1.2.1 시간 복잡도
알고리즘에 주로 나오는 시간 복잡도를 시간이 증가하는 순서로 나열했습니다.
▼ 표 1-1 시간 복잡도의 종류
|
이름 |
표기법 |
|
상수(constant) 시간 |
O(1) |
|
로그(logarithmic) 시간 |
O(logn) |
|
선형(linear) 시간 |
O(n) |
|
N 로그 N(N Log N) 시간 |
O(nlogn) |
|
이차(quadratic) 시간 |
O(n2) |
|
다항(polynomial) 시간 |
O(nc), c는 1보다 큰 상수 |
|
지수(exponential) 시간 |
O(cm), c는 1보다 큰 상수 |
|
계승(factorial) 또는 n의 n승(N-power-N) 시간 |
O(n!) 또는 O(nn) |
시간 복잡도의 증가율은 다음과 같습니다.
▼ 표 1-2 시간 복잡도의 증가율
|
N |
함수 증가율(추정치) |
||||||
|
O(1) |
O(logn) |
O(n) |
O(nlogn) |
O(n2) |
O(n3) |
O(2n) |
|
|
10 |
1 |
3 |
10 |
30 |
102 |
103 |
103 |
|
102 |
1 |
6 |
102 |
6x102 |
104 |
106 |
1030 |
|
103 |
1 |
9 |
103 |
9x103 |
106 |
109 |
10300 |
|
104 |
1 |
13 |
104 |
13x104 |
108 |
1012 |
103000 |
|
105 |
1 |
16 |
105 |
16x105 |
1010 |
1015 |
1030000 |
|
106 |
1 |
19 |
106 |
19x106 |
1012 |
1018 |
10300000 |
알고리즘을 실행하는 데 걸리는 시간이 함수 증가율에 따라 크게 달라지는 것을 볼 수 있습니다. 같은 데이터 집합을 사용해도 어떤 알고리즘은 몇 분 만에 결과를 계산하지만, 어떤 알고리즘은 며칠 동안 실행해도 결과를 계산하지 못합니다.