2.1.2 시간 복잡도 그래프
빅오 표기법으로 나타낼 수 있는 시간 복잡도는 대략 O(1), O(logn), O(n), O(nlogn), O(n2), O(2n), O(n!)이며, 다음 그림에서 각각 어느 정도의 시간을 소모하는지 확인할 수 있습니다.
▲ 그림 2-2 시간 복잡도 그래프
각 시간 복잡도에 따른 연산 횟수를 정리하면 다음과 같습니다.
▼ 표 2-1 입력 데이터 수에 따른 시간 복잡도의 연산 횟수
|
시간 복잡도 |
입력 데이터 수(n) |
||||||
|
1 |
2 |
4 |
8 |
16 |
32 |
64 |
|
|
O(1) |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
|
O(logn) |
0 |
1 |
2 |
3 |
4 |
5 |
6 |
|
O(n) |
1 |
2 |
4 |
8 |
16 |
32 |
64 |
|
O(nlogn) |
0 |
2 |
8 |
24 |
64 |
160 |
384 |
|
O(n2) |
1 |
4 |
16 |
64 |
256 |
1024 |
4096 |
|
O(2n) |
2 |
4 |
16 |
256 |
65536 |
4294967296 |
표현 불가 |
|
O(n!) |
1 |
2 |
24 |
40326 |
20922789888000 |
2.6313084e+35 |
표현 불가 |