[CS300 #061] 점근 표기법 — 빅오·빅오메가·빅세타를 정의대로 읽기

컴퓨터공학 300 주제 시리즈의 061번째 글이다. 전체 지도는 여기.

한 줄 요약

점근 표기법은 입력 크기 n 이 충분히 커졌을 때 함수가 얼마나 빨리 자라는지를 상수 배를 무시하고 비교하는 언어다. O 는 위로 막고, Ω 는 아래로 받치고, Θ 는 양쪽을 다 잡는다.

왜 필요한가

같은 알고리즘이라도 실행 시간은 기계, 언어, 컴파일러, 캐시 상태에 따라 달라진다. 노트북에서 0.3초 걸린 코드가 서버에서는 0.1초 걸릴 수 있다. 이런 숫자로는 “이 알고리즘이 저 알고리즘보다 낫다” 를 말할 수 없다.

그래서 기계에 묶인 상수를 떼어 내고, 입력이 커질 때 비용이 어떻게 자라는지만 본다. n 이 두 배가 될 때 시간이 두 배가 되는지, 네 배가 되는지, 거의 그대로인지가 핵심이다. 이 성장률을 정확하게 말하기 위한 도구가 점근 표기법이다.

시리즈 4부의 주제문은 “외우는 게 아니라 왜 이 시간 안에 끝나는가를 설명할 수 있어야 한다” 이다. 그 설명은 언제나 이 표기법으로 끝난다.

핵심 개념

세 가지 정의

함수 f(n), g(n) 은 음이 아닌 값을 갖는다고 하자.

표기	정의	읽는 법
f(n) = O(g(n))	양의 상수 c, n0 가 있어서 n ≥ n0 이면 0 ≤ f(n) ≤ c·g(n)	f 는 g 보다 빨리 자라지 않는다 (상한)
f(n) = Ω(g(n))	양의 상수 c, n0 가 있어서 n ≥ n0 이면 0 ≤ c·g(n) ≤ f(n)	f 는 g 보다 느리게 자라지 않는다 (하한)
f(n) = Θ(g(n))	양의 상수 c1, c2, n0 가 있어서 n ≥ n0 이면 c1·g(n) ≤ f(n) ≤ c2·g(n)	f 와 g 는 같은 속도로 자란다

Θ(g) 는 O(g) 이면서 동시에 Ω(g) 인 것과 같다. 이 정의는 Knuth 가 1976년 SIGACT News 에 쓴 글에서 정리한 형태가 오늘날 교과서의 표준이 되었다.

정의대로 증명해 보기

f(n) = 3n² + 10n + 5 가 Θ(n²) 임을 보이자.

상한: n ≥ 1 이면 10n ≤ 10n², 5 ≤ 5n² 이다. 그러므로 f(n) ≤ 3n² + 10n² + 5n² = 18n². c2 = 18, n0 = 1.
하한: 모든 n ≥ 1 에서 f(n) ≥ 3n². c1 = 3.

두 상수를 찾았으니 끝이다. 낮은 차수 항과 계수가 사라지는 이유가 바로 이것이다. “버린다” 가 아니라 “상수 c 안에 흡수된다” 가 정확한 말이다.

등호는 등호가 아니다

f(n) = O(n²) 의 = 는 사실 집합 소속 ∈ 이다. O(n²) 는 “c·n² 아래에 머무는 함수들의 집합” 이다. 그래서 n = O(n²) 는 참이지만 n² = O(n) 은 거짓이다. 좌우를 바꿀 수 없다.

같은 이유로 “이 알고리즘은 O(n²) 이다” 는 틀린 말은 아니지만 정보가 적을 수 있다. 선형 탐색도 O(n²) 에 속한다. 상한이 꽉 끼는지까지 말하려면 Θ 를 쓴다.

작은 o 와 작은 ω

f = o(g): 모든 양의 c 에 대해 충분히 큰 n 에서 f(n) < c·g(n). 극한으로 쓰면 f/g → 0. “엄밀히 더 느리게 자란다”.
f = ω(g): f/g → ∞. “엄밀히 더 빨리 자란다”.

n = o(n²) 이지만 n² ≠ o(n²) 이다.

자주 보는 성장률 순서

1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!

로그의 밑은 상관없다. log₂ n = log₁₀ n / log₁₀ 2 이므로 밑을 바꾸면 상수 배만 달라진다. 그래서 그냥 log n 이라고 쓴다.

최악·평균·최선과 O·Ω·Θ 는 다른 축이다

초급자가 가장 많이 섞는 부분이다.

최악·평균·최선은 어떤 입력을 볼지 고르는 축이다.
O·Ω·Θ 는 고른 함수를 어떻게 묶어 말할지 고르는 축이다.

삽입 정렬의 최악 실행 시간은 Θ(n²) 이고, 최선 실행 시간은 Θ(n) 이다. “최선은 Ω, 최악은 O” 같은 대응은 없다. 두 축은 독립이다.

직접 해 보기

증가율 차이를 숫자로 본다. 아래 코드는 python3 로 실행해 확인했다.

def count_ops(n):
    lin = n
    nlogn = 0
    k = n
    while k > 1:          # 바닥 log2 n 번 반복
        k //= 2
        nlogn += n
    quad = n * n
    return lin, nlogn, quad

print(f"{'n':>8} {'n':>10} {'n log n':>12} {'n^2':>14}")
for n in [10, 100, 1000, 10000, 100000]:
    a, b, c = count_ops(n)
    print(f"{n:>8} {a:>10} {b:>12} {c:>14}")

# 상수 계수는 결국 진다: 100n vs n^2
for n in [10, 50, 100, 101, 1000]:
    print(n, 100 * n, n * n)

출력:

       n          n      n log n            n^2
       10           30            100
      100          600          10000
     1000         9000        1000000
    10000       130000      100000000
  100000     100000      1600000    10000000000
1000 100
5000 2500
10000 10000
10100 10201
100000 1000000

두 가지가 보인다. 첫째, n 이 10만이면 n² 은 n log n 의 6천 배가 넘는다. 둘째, 100n 은 n ≤ 100 까지는 n² 보다 크지만 n = 101 부터 역전된다. 정의의 n0 가 바로 이 역전점이다. 점근 표기는 “충분히 큰 n” 에서의 이야기라는 점을 잊으면 안 된다.

현업에서는

라이브러리 문서가 이 언어로 쓰여 있다. Java ArrayList 문서는 add 가 “amortized constant time” 이라고 적는다. Python bisect 문서는 탐색은 O(log n) 이지만 삽입은 O(n) 이동이 지배한다고 경고한다. 문서를 읽으려면 표기법을 알아야 한다.
작은 n 에서는 상수가 이긴다. 많은 표준 정렬 구현이 작은 구간에서 삽입 정렬로 바꾸는 이유다. 점근적으로 나쁜 알고리즘이 n 이 작을 때는 더 빠르다.
장애는 n 이 커질 때 터진다. 테스트 데이터 100건에서 멀쩡하던 이중 루프가 운영 데이터 100만 건에서 멈춘다. 홈랩 클러스터에서도 로그 수집 스크립트가 파드 수가 늘자 갑자기 느려지는 일은 대개 어딘가 숨은 O(n²) 때문이다.
코드 리뷰의 공용어다. “이 부분 n 에 대해 제곱이네요” 한 마디로 문제를 정확히 전달할 수 있다.

확인 문제

f(n) = 5n + 20 이 O(n) 임을 보이는 상수 c, n0 를 하나 제시하라.
2ⁿ⁺¹ = O(2ⁿ) 인가? 2²ⁿ = O(2ⁿ) 인가?
“퀵 정렬은 최악에 O(n²), 최선에 Ω(n log n) 이다” 라는 문장에서 어색한 점은 무엇인가?
log₂ n 과 log₁₀ n 이 같은 Θ 클래스에 속하는 이유를 한 줄로 설명하라.

풀이

n ≥ 1 이면 20 ≤ 20n 이므로 5n + 20 ≤ 25n. c = 25, n0 = 1. (c = 6, n0 = 20 도 된다.)
2ⁿ⁺¹ = 2·2ⁿ 이므로 O(2ⁿ) 이다. 2²ⁿ = 4ⁿ 이고 4ⁿ/2ⁿ = 2ⁿ → ∞ 이므로 O(2ⁿ) 가 아니다. 지수의 상수는 흡수되지 않는다.
입력 경우(최악·최선)와 표기(O·Ω)를 짝지어 쓴 점이다. 정확히는 “최악 실행 시간은 Θ(n²), 최선 실행 시간은 Θ(n log n)” 처럼 각 경우에 꽉 낀 표기를 쓰는 게 좋다.
둘은 상수 1/log₁₀2 배만큼만 다르기 때문이다.

더 읽을거리 (References)

Donald E. Knuth, “Big Omicron and big Omega and big Theta”, ACM SIGACT News 8(2), 1976.
NIST Dictionary of Algorithms and Data Structures, big-O notation
Python 공식 문서, bisect — Array bisection algorithm
Cormen, Leiserson, Rivest, Stein, Introduction to Algorithms, 4th ed., MIT Press, 2022, 3장.