시간복잡도 또는 점근표기법
알고리즘의 수행시간(명령이 실행되는 횟수)를 나타내는 방법
1. Big O 표기법
알고리즘 수행시간의 상한(최악의 경우)을 나타낸 표기법
함수 |
설명 |
알고리즘 |
O(1) |
해당 알고리즘이 최악의 경우에도 일정한 상수 시간에 종료된다는 것을 의미한다. |
해시테이블 |
O(log2n) |
최악의 경우에도 입력값 n이 증가하는 속도보다 수행시간이 증가하는 속도가 느린 알고리즘의 성능을 나타낸다. 이러한 성능을 가진 알고리즘은 n이 10일 때 수행 시간이 3.32이며 n이 10000이 됐을 때도 여전히 13.29에 불과하다. 입력이 1000배가 늘어나도 수행 시간은 고작 4배 정도 늘어난다. |
이진 탐색 |
O(n) |
최악의 경우 입력 값 n만큼의 수행 시간을 요구하는 성능이다. 입력값 n이 증가하는 속도만큼 수행 시간도 같은 속도로 증가한다. |
순차 탐색 |
O(nlogn) |
로그함수가 사용되기는 했지만, O(log2N)와는 비교할 수 없을 정도로 수행시간이 길다. O(n) 알고리즘보다 훨씬 수행시간이 길다. |
병합 정렬, 퀵 정렬 |
O(n2) |
최악의 경우 입력값 n에 대해 제곱으로 수행시간이 늘어나는 성능이다. 똑같이 n회만큼 반복하도록 되어 있는 for문이 2개 중첩되어 있으면 이러한 성능이 나온다. |
버블 정렬, 삽입 정렬 |
O(n3) |
이러한 성능의 알고리즘은 입력값 n에 대해 3제곱으로 수행시간이 증가한다. |
행렬 곱셈 |
O(2n) |
입력값 n에 대해 최대 2의 n제곱만큼 수행시간이 증가하는 경우이다. n이 10이라고 해도 수행시간은 1024가 된다. |
|
2. Big Omega 표기법
알고리즘 수행시간의 하한(최상의 경우)을 나타낸 표기법
3. Big Theta 표기법
알고리즘 수행시간의 평균(평균의 경우)를 나타낸 표기법. O 표기법과 Omega 표기법을 모두 만족시키는 증가함수