시간복잡도

참고자료 출처 : https://blog.encrypted.gg/922

( 이 게시판의 포스팅들은 해당 블로그의 내용을 공부하는 포스팅이다.

     정확한 내용이나 자세한 내용은 해당 블로그에서 참고바란다. )

 

컴퓨터는 1초에 대략 3~5억 개 정도의 연산을 처리할 수 있다.

처리하는 행위가 복잡한 연산을 요하는지에따라 차이가 있을 수 있다.

 

즉, 제한시간이 1초라면 코드는 3~5억번의 연산내에 처리돼야 한다.

 

변수를 선언하고 초기화하는 것 역시 컴퓨터의 연사을 필요로 한다.

for문의 경우에는 for문의 반복횟수를 결정하는 인자의 값을 선언하고 초기화하고,

반복횟수마다 그 값이 반복문을 반복시키는 결정하는 인자와 비교하고,

반복횟수를 결정하는 인자의 값을 증가시키는

연산이 발생하게 된다.

 

물론 이러한 과정을 매 횟수마다 계산할 필요는 없다.

대략적으로 반복문이 포함된 경우에는 n번의 연산이 발생한다고 칭하게된다.

 

반복문의 다른 경우를 이야기해보면,

100명의 사람들이 '이름이 가나다' 순으로 서 있다고 했을때, 원하는 이름을 가진 사람을 찾아내는데 걸리는 시간을

생각해보자. ( 한 사람의 이름을 확인하는데 소요되는 시간은 1초로 가정한다. )

 

업다운 게임 처럼, 가운데 사람의 이름을 묻고 순서상 원하는 이름이 앞인지 뒤인지 확인하고

다시 그 그룹의 가운데 사람에게 묻는 방식으로 진행할 수 있다.

 

이 경우 대략 log100의 시간이 평균적으로 소요된다. ( 최소 1초, 최대 logN초 )

즉 n명의 경우 logn에 비례해서 시간복잡도를 계산할 수 있다.

 

( 밑이 2인 로그만 나온다고 하니 참고하자. )

 

이러한 내용이 시간복잡도 이고,

빅오 표기법으로 표기한다.

O(n), O(n^2), O(logn) 등이 있으며 크기는 

 

O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(2^n) < O(n!)

이러한 순서이다. 

더 깊게 들어가면 수학의 입실론 델타라는 것을 이용해 빅오 표기법을 정의하고,

빅/스몰 오,세타,오메가 라는 개념이 있으나 공부에 우선순위를 둬 다루지 않겠다.

 

주로 O(2^n), O(n!) 같은 시간복잡도를 갖는 코드는

n이 작은 경우가 아니라면 굉장히 높은 시간복잡도를 갖기때문에 사용하기 어렵다.

 

(출처 : https://blog.encrypted.gg/922 )

 

이 표를 보면 이러한 연산을 동시에 몇명의 유저가 이용할지 고려해보는 것도 좋을 것 같다.

하나의 로직이 사용되는 것도 아니기때문에, 최대한 NlogN 혹은 N정도의 시간복잡도를 갖도록 하는 것이 좋겠다.

해당 표는 절대적인 수치는 아니고, 추정치이기 때문에 참고하자.

 

시간복잡도가 O(1), O(n), O(n^2) 등은 직관적이므로 제외하고,

개인적으로 복잡하게 느껴졌던 O(logn)을 풀이하겠다.

 

<문제>

n이하의 수 중에서 가장 큰 2의 거듭제곱수를 반환하는 함수 solution(int n)을 작성하라.
n은 10억 이하의 자연수이다.

 

private static int solution(int n) {
		int result = 1;
        
//		for (int i = 0; i < n; i++) {
//			if(Math.pow(2, i)<=n) {
//				result = (int) Math.pow(2, i);
//			}else break;
//		}
		
//		for (int i = 0; i < n; i++) {
//			if(result*2<=n) result *= 2;
//			else break;
//		}
		
		while(result*2<=n) result *=2;
		
		return result;
	}

 

( 한번에 마지막 코드 처럼 작성하게되는 날이 오길 바라며.. )

 

이때 n은 2의 k승이상 k+1미만 이라고 할때, result는 while문 안에서 최대 k번까지 커진다.

result는 2^k가 되고,  시간복잡도는 O(k)가 된다. 이때 로그의 정의에 따라 k = logn이므로

O(logn)이 된다. 

직관적으로 이 내용이 다가오지 않았어서 첨언하면

k = log 2^k 

이다.

자세한 내용은 못 봤으나 이진법이라 그런건지 log의 밑은 2를 default로 생각한다고 한다.