§ 1 · 공통 언어단계 세기의 언어
Big O 표기법은 시간 단위 대신 알고리즘이 거치는 단계의 수에만 집중함으로써 일관성을 얻는다. 그리고 그 단계 수가 데이터가 증가할 때 어떻게 변하는지를 묻는다.
1장에서 배열 읽기는 크기와 관계없이 1단계였다. Big O로는 이렇게 쓴다.
선형 탐색은 최악의 경우 배열의 원소 수만큼 단계를 거친다.
§ 2 · 수평선과 대각선상수 시간 vs 선형 시간
그래프 위에서 O(1)은 완벽한 수평선이다. 데이터가 늘어도 단계 수가 일정하기 때문이다. O(N)은 완벽한 대각선이다. 추가 데이터마다 1단계씩 늘기 때문이다.
흥미로운 점 — 항상 100단계를 수행하는 알고리즘도 일정하기만 하면 O(1)이다. 100단계 O(1)은 1단계 O(1)보다 덜 효율적이지만, 그래도 모든 O(N) 알고리즘보다 결국 빠르다. 어느 지점부터는 O(N)이 100을 넘어 무한대까지 더 많은 단계를 쓰기 때문이다.
§ 3 · 지수의 역로그란 무엇인가
이진 탐색은 O(1)도 O(N)도 아니다. 둘 사이 어딘가에 있다. Big O는 이를 O(log N)으로 설명한다. 이해하려면 먼저 로그를 알아야 한다.
로그(logarithm)는 지수의 역이다. 2³ = 2 × 2 × 2 = 8이다. 그렇다면 log₂ 8은 그 반대를 묻는다 — "8을 얻으려면 2를 몇 번 곱해야 하나?" 답은 3이다.
§ 4 · 두 배에 1단계O(log N) 설명
O(log N)은 사실 O(log₂ N)의 줄임말이다. 편의상 작은 2를 생략한다. 의미는 이렇다 — O(log N)은 데이터를 반씩 계속 나눠 1개가 남을 때까지 걸리는 단계 수다. 8개 원소면 3단계, 16개면 4단계.
달리 말하면 데이터가 두 배가 될 때마다 1단계만 추가되는 알고리즘이다. 이진 탐색이 정확히 이렇게 한다.
| N 원소 | O(N) | O(log N) |
|---|---|---|
| 8 | 8 | 3 |
| 64 | 64 | 6 |
| 256 | 256 | 8 |
| 1024 | 1024 | 10 |
효율성 순서대로(가장 빠른 것부터): O(1) → O(log N) → O(N). O(log N)은 살짝 위로 휜 곡선으로, O(1)보다는 덜 효율적이지만 O(N)보다는 훨씬 효율적이다.
§ 5 · 코드에 적용실제 코드 예제
리스트의 모든 항목을 출력하는 for 루프는, 원소가 4개면 4단계·10개면 10단계를 거친다. 원소 수만큼 단계를 거치니 O(N)이다.
def is_prime(number): for i in range(2, number): if number % i == 0: return False return True
여기서 데이터는 배열이 아니라 함수에 전달된 숫자 그 자체다. is_prime(7)이면 루프가 약 7단계, is_prime(101)이면 약 101단계를 돈다. 단계 수가 전달된 숫자와 발맞춰 증가하므로 O(N)의 전형이다. 반면 print('Hello world!')는 항상 1단계 — O(1)이다.
§ 6 · 정리이 장이 남긴 것
Big O 표기법을 손에 넣었으니, 이제 임의의 두 알고리즘을 일관된 체계로 비교할 수 있다. 다음 장부터는 이 도구로 실제 코드를 측정하고, 느린 알고리즘을 더 빠른 Big O 등급으로 끌어올리는 법을 배운다.