시간복잡도 계산

시간복잡도

기본적인 연산을 수행하는데에 어떤 고정된 시간이 걸릴 때, 알고리즘에 의해서 수행되는 기본 연산의 개수를 세어 예측할 수 있다. 그러므로 걸리는 시간의 총량과 알고리즘에 의해 수행되는 기본적인 연산의 개수는 최대 상수 인자만큼 다르다.

- 위키피디아-

 

시간복잡도를 구하는 방법은 아래와 같이 크게 3가지이다.

• O(Big-O)
• Ω(Omega)
• Θ(Theta)

 

가장 많이 쓰이는 시간복잡도는 빅오(Big-O) 표기법이므로 해당 표기법에 대한 설명을 다뤄볼 것이다.

 

코드를 예시로 하여 좀 더 알아보면 아래 두개의 코드를 한번 자세히 읽어보도록 한다.

int sum = 0; for (int i=0; i<N; i++){      sum +=i; }

int sum = (N+1)*N/2;

n의 변수가 있다는 가정하에 두개의 코드를 보면 몇번 연산 및 계산이 되는지 생각을 해보면 된다.

 

먼저 첫번째 코드는 N 까지 가기까지 위해 

sum = 0;  // 1번

i = 0;  // 1번

i++;  // N번

sum = sum+i;  // N번

이렇게 되서 총 2N +2 번의 연산이 필요하다.

 

아래 코드는 sum을 구하기 위해서는 

N+1  // 1번

*N  // 1번

/2  // 1번

이렇게 해서 총 3번의 연산이 들어간다.

 

bigO 표기법의 특성은 상수랑 차항 계수만 표시되기에 첫번째 함수는 O(n) 이고 두번째는 O(1) 이다.

즉 아래의 코드가 시간 복잡도 상에서는 더 유리하다는 뜻이다.

 

좀더 알아보기 위해서 이중 반복문을 예시로 한번 더 들어보면

int sum = 0; for(int i = 0; i<N; i++){      for(int j = 0; j<i; j++){           sum += j; }}

int sum = 0; for(int i =N; i>0; i/=2){      for(int j = 0; j<i; j++){           sum += j; }}

첫번째 코드를 보면 

바깥 반복문에서 i는 0부터 N-1까지 변하며, 안쪽 반복문은 해당하는 i만큼 반복하므로,

sum = sum+j 가 돌아가는 코드는 첫번째 반복분에서는 0번

두번째 i 일땐 1번 ,....

즉, 0+1+2+…+(N-1) = N*(N-1)/2 번 반복합니다.

등차수열의 합 공식과 동일합니다.

 

두번째 코드는 바깥쪽 반복문이 log N번 반복하고, 안쪽 반복문은 i의 값에 따라 반복 횟수가 다르다.

i는 N부터 1까지 변하며, 안쪽 반복문은 해당하는 i만큼 반복하므로, N + N/2 + N/4 + … + 1 = 2N 번 반복하고, Big-O로 표기하면 2N = O(N)이 된다.

 

그럼 역시 bigO 표기법에 따라 첫번째는 O(n²) 이고 두번째는 O(N) 이 되어 두번째 코드가 더욱 효율적인 코드가 된다.

 

각 시간복잡도에 대한 크고 작음은 다음 그림을 참고하도록 한다.

참고로 각 스텝마다 사용되는 예시는 아래와 같다.
O(1) : 스택의 Push, Pop
O(log n) : 이진트리
O(n) : for 문
O(n log n) : 퀵 정렬(quick sort), 병합정렬(merge sort), 힙 정렬(heap Sort)
O(n²): 이중 for 문, 삽입정렬(insertion sort), 거품정렬(bubble sort), 선택정렬(selection sort)
O(2ⁿ) : 피보나치 수열