다음 표는 O(N)과 O(logN)의 효율성에 엄청난 차이가 있음을 보여준다.
▼ 표 3-1
|
원소 개수(N) |
O(N) |
O(logN) |
|
8 |
8 |
3 |
|
16 |
16 |
4 |
|
32 |
32 |
5 |
|
64 |
64 |
6 |
|
128 |
128 |
7 |
|
256 |
256 |
8 |
|
512 |
512 |
9 |
|
1024 |
1024 |
10 |
O(N) 알고리즘에는 데이터 원소 수만큼의 단계가 필요한 반면, O(logN) 알고리즘에는 데이터 원소가 두 배로 늘어날 때마다 딱 한 단계만 더 필요하다.
이어지는 장에서는 지금까지 배운 세 가지 빅 오 표기법뿐 아니라 다른 범주에 해당하는 알고리즘도 만나볼 것이다. 하지만 그 전에 우선 일상적인 코드에 이러한 개념을 적용해 보자.