▼ 표 2-2 시간 복잡도별 N 크기에 따른 계산 결과(정수로 반올림)
|
|
10 |
20 |
100 |
10,000 |
1,000,000 |
100,000,000 |
|
O(1) |
1 |
1 |
1 |
1 |
1 |
1 |
|
O(logN) |
3 |
4 |
7 |
13 |
20 |
27 |
|
O(N) |
10 |
20 |
100 |
10,000 |
1,000,000 |
100,000,000 |
|
O(N logN) |
33 |
86 |
664 |
132,877 |
- |
- |
|
O(2N) |
1,024 |
1,048,576 |
- |
- |
- |
- |
|
O(N!) |
3,628,800 |
- |
- |
- |
- |
- |
잠깐만요
O(logN) 표기는 log2 N을 나타낼 때가 많습니다. 따라서 표 2-2에서 계산 값도 log2 N의 값을 계산한 결과입니다. log2 N을 왜 O(logN)으로 표기하는지는 ‘2.2절 시간 복잡도 계산하기’에서 다룹니다.
표 2-2에서 확인할 수 있듯이, N이 커질수록 시간 복잡도의 결괏값 차이는 굉장히 커집니다. 이는 그래프로도 확연히 드러납니다. 다음 그림은 자주 등장하는 시간 복잡도인 O(1), O(logN), O(N), O(N logN), O(N2), O(2N), O(N!)의 비교 그래프입니다.