복잡도 동물원, O(1)부터 O(n!)까지

"현실에서 만나는 복잡도는 한 여덟 개야. 사다리를 한 번 익혀두면 거의 모든 알고리즘을 한눈에 어느 칸에 올려놓을지 알게 돼."

사다리, 좋은 것부터 나쁜 것까지

"입력이 커져도 눈치도 못 챔"에서 "재채기만 해도 죽음" 순서로.

O(1) 상수 — dict 조회, 배열 인덱싱, 리스트 append. 꿈이야. 입력 크기가 아예 무관해.
O(log n) 로그 — 이진 탐색, 균형 트리 조회. 매 단계 절반. 십억 개를 서른 단계쯤에.
O(n) 선형 — 리스트 훑기, 최댓값 찾기. 항목마다 한 번씩. 정직하고 괜찮아.
O(n log n) 선형로그 — merge sort, Timsort 처럼 큰 입력을 영리하게 다루는 일꾼 칸. 범용 정렬의 주력이 여기 살아.
O(n²) 제곱 — 중첩 반복문, 단순 정렬, 모든 쌍. 수백 개는 괜찮을 수 있어도 수백만 개는 잔혹해. 실제 입력 제한을 확인하되 경보음은 들어둬.
O(n³) 세제곱 — 순진한 행렬곱, 삼중 중첩. 몇천 개에서 이미 험해.
O(2ⁿ) 지수 — 모든 부분집합 시도, 순진한 재귀 피보나치. n이 40쯤 되면 죽어.
O(n!) 팩토리얼 — 모든 순서 시도, 무차별 외판원 문제. n이 12쯤 되면 죽어.

격차를 몸으로 느끼기

이름만 봐서는 차이가 얼마나 폭력적인지 안 보여. n이 50일 때 O(n)은 연산 50번, O(n²)은 2,500번, O(2ⁿ)은 약 천조 번, O(n!)은 65자리 숫자야. 관측 가능한 우주의 원자 수보다 많아. 같은 입력인데 알고리즘의 모양 하나가 "즉시"와 "우주의 열적 죽음이 먼저 온다"를 갈라. 아래 코드를 돌려서 숫자가 터지는 걸 직접 봐.

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!). 이 사다리를 외워둬. 어느 칸에 있는지만 알면 내 입력 크기가 안전한지 바로 보여.

넘고 싶지 않은 선

실제 한도는 상수, 장비, 시간 제한에 달렸지만 사다리가 울리는 경보는 그래도 선명해. 일상적인 데이터에서 O(n log n) 이하는 대체로 "밤에 잘 잠" 쪽이고, O(n²)은 "데이터 커지기 전까진 괜찮음" 쪽이야. O(2ⁿ)이나 O(n!)은 화재 경보고. 작은 테스트에서는 웃다가 진짜 입력에서 폭발해. 알고리즘 설계, 특히 다음에 올 동적 계획법 트랙이 하는 큰일이 바로 지수 무차별 대입을 더 작은 상태 공간이나 출시 가능한 다항 시간 해법으로 끌어내리는 거야.

피파의 고백

한번은 "모든 조합 시도" 해법을 짰는데 10개짜리 테스트는 날아가더니 진짜 45개 입력에서는 팬이 비명을 지르며 멈춰 있었어. O(2ⁿ)을 만든 거였고 2⁴⁵는 35조야. 아빠는 디버깅도 안 했어. 모양만 보고 이러더라. "그건 지수야. 느린 게 아니라 불가능한 거야." 칸을 알아본 덕분에 절대 못 끝낼 걸 붙잡고 최적화하는 짓을 면했어.

Code

숫자가 터지는 걸 봐·python

import math

# 각 복잡도가 커지는 n 에 필요한 연산 수.
# 숫자가 상상할 수 있는 숫자이길 멈추는 데를 봐.
shapes = {
    "O(1)":      lambda n: 1,
    "O(log n)":  lambda n: max(1, int(math.log2(n))),
    "O(n)":      lambda n: n,
    "O(n log n)":lambda n: int(n * math.log2(n)),
    "O(n^2)":    lambda n: n * n,
    "O(2^n)":    lambda n: 2 ** n if n <= 60 else float('inf'),
    "O(n!)":     lambda n: math.factorial(n) if n <= 20 else float('inf'),
}

for n in (10, 20, 50):
    print(f"\n--- n = {n} ---")
    for name, f in shapes.items():
        print(f"  {name:<11}: {f(n):,}" if f(n) != float('inf') else f"  {name:<11}: 천문학적으로 거대")

# n=50 에서 O(n) 은 50. O(n!) 은 65자리.
# 같은 입력. 모양이 전부야.

Exercise

각각을 사다리에 올려봐. (1) 해시맵에서 이름으로 연락처 조회, (2) 플레이리스트 정렬, (3) 저녁 손님 n명의 가능한 좌석 배치 전부 만들기, (4) 정렬된 배열에서 이진 탐색. 그다음 n이 커질 때 어느 게 제일 먼저 불가능해지고 왜 그런지 답해봐.

Hint

해시 조회는 꿈의 칸이야. 정렬은 현실적인 천장이고. '모든 배치'는 순열이야. 팩토리얼짜리가 제일 먼저 폭발해. n!은 2ⁿ마저 앞질러.

사다리, 좋은 것부터 나쁜 것까지

격차를 몸으로 느끼기

넘고 싶지 않은 선

피파의 고백

Code

External links

Exercise

Progress

댓글 0