시간 복잡도(Time Complexity)
검색 알고리즘을 보다가 드디어 헷갈리던 복잡도 얘기가 나왔다.
헷갈려하던 부분이므로 따로 빼서 정리해보았다.
Complexity
프로그램의 실행 속도는 프로그램이 동작하는 하드웨어, 컴파일러 등의 조건에 따라 달라진다. 알고리즘의 성능을 객관적으로 평가하는 기준을 복잡도(Complexity)라고 한다.
복잡도는 시간 복잡도(Time Complexity)와 공간 복잡도(Space Complexity)가 있다.
- 시간 복잡도: 실행에 필요한 시간을 평가한 것
- 공간 복잡도: 기억 영역과 파일 공간이 얼마나 필요한가를 평가한 것
여기서는 시간 복잡도에서만 한번 정리해보았다.
소수 찾기 알고리즘에서 알고리즘을 선택할 때 이 복잡도의 균형을 생각할 필요성이 있는 것을 알 수 있다.
Time Complexity
Linear Search Time Complexity
/* */ static int seqSearch(int[] a, int n, int key){
/*1*/ int i = 0;
/*2*/ while(i < n){
/*3*/ if(a[i] == key)
/*4*/ return i;
/*5*/ i++;
/* */ }
/*6*/ return -1;
/* */ }
각 단계 별 시간 복잡도는 아래와 같다.
| 단계 | 실행 횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | n/2 | O(n) |
| 3 | n/2 | O(n) |
| 4 | 1 | O(n) |
| 5 | n/2 | O(n) |
| 6 | 1 | O(1) |
1 단계에서는 변수 i에 0을 한번 대입한 후로 실행되지 않는다.
이렇게 한번만 실행되는 경우 시간 복잡도는 O(1)로 표기한다.
4, 6 단계 또한 return은 메서드 종료를 의미하므로 한번만 실행된다. 따라서 시간 복잡도는 O(1)이다.
2, 3 단계의 평균 실행 횟수는 n/2회이다. 따라서 시간 복잡도는 O(n)이다.
실행 횟수가 n/2회지만 O(n)으로 표기하는 이유는 n이 무한히 커졌을 때를 가정하면 값의 차이가 거의 없기 때문이다. 따라서 100번 실행되는 경우도 O(100)이 아니라 O(1)로 표기한다.
이와 비슷한 맥락으로 O(n+1)이나, O(n)은 컴퓨터에게 큰 차이가 없게 된다. 따라서 총 시간 복잡도를 구하면 O(1+n+n+1+n+1)이 되므로, 총 시간 복잡도는 O(n)이다.
Binary Search Time Complexity
/* */ static int binSearch(int[] a, int n, int key){
/* 1*/ int front = 0;
/* 2*/ int rear = n - 1;
/* */
/* */ do{
/* 3*/ int center = (front + rear) / 2;
/* 4*/ if(a[center] == key)
/* 5*/ return center;
/* 6*/ else if(a[center] < key)
/* 7*/ front = center + 1;
/* */ else
/* 8*/ rear = center - 1;
/* 9*/ }while(front <= rear);
/* */
/*10*/ return -1;
/* */ }
각 단계 별 시간 복잡도는 아래와 같다.
| 단계 | 실행 횟수 | 복잡도 |
| 1 | 1 | O(1) |
| 2 | 1 | O(1) |
| 3 | log n | O(log n) |
| 4 | log n | O(log n) |
| 5 | 1 | O(1) |
| 6 | log n | O(log n) |
| 7 | log n | O(log n) |
| 8 | log n | O(log n) |
| 9 | log n | O(log n) |
| 10 | 1 | O(1) |
따라서 총 시간 복잡도는 O(1+1+log n+log n+1+log n+log n+log n+log n+1) = O(log n)
여기서 시간복잡도가 O(log n)인 부분은 내가 항상 어려워하던 부분이다.
n번이면 n번이고, 1번이면 한 번이지 log n번은 대체 무슨 이유로 log n번인가!
이번에도 책에 상세한 설명이 없어서 한번 검색으로 찾아봤다.
이 그래프를 보면 조금 이해가 갈 지도 모르겠다.
여기서 log n을 보면 시간에 따라 조금씩 증가하는 것을 볼 수 있다. 단계 3, 4, 6, 7, 8, 9의 코드를 보면, 항상 n/2번이 실행되지 않는다. center값이 key가 되어 금방 찾을 수도 있고, 끝까지 n/2번 실행하여 답을 찾을 수 없을 수도 있다.
03/09 수정
누구나 자료구조와 알고리즘 책을 읽다가 이진 검색의 빅오 계산 부분을 보게 되었다. 설명을 읽다가 전에 적은 설명보다 이 설명이 더 좋을 것 같아 글을 수정한다.
먼저 빅오 표기법은 가장 최악의 시나리오에서의 효율성이다. 이전에는 이 점을 간과했다. 중간에 끝날 수도 있다고 생각하는 것이 아니라, 끝까지 계산했을 때로 가정한다.
코드 단위로 생각하기보다는, 전체적인 그림을 그려서 생각하는 것이 더 편한 것 같다. 배열 크기가 3일 때 최대 단계 수는 2이다. 배열 크기가 7이 되면 최대 단계 수는 3이 된다.
배열이 두배로 증가할 때마다 최대 단계 수가 한 단계씩 늘어나고 있다.
이런 경우를 평균적으로 log n번 실행된다고 한다.즉 O(log n)은 데이터가 두 배로 증가할 때마다 한 단계씩 늘어나는 것을 의미한다. 쉽게 보자면 그냥 n번 실행되지도 않고, 1번 실행되지도 않으니 그 중간인 log n번 실행된다고 보는 게 편할 것 같다.
수학적 계산은 어렵다…
시간 복잡도의 대소 관계는 아래와 같다.
그래프를 보고 착각하지 말아야 할 것은, n^3보다 2^n이 n이 커질 수록 증가속도가 더 빠르다는 것이다.
1 < log n < n < nlog n < n^2 < n^3 < n^k < 2^n