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

"현실에서 만나는 복잡도는 한 여덟 개야. 사다리를 한 번 익히면 거의 모든 알고리즘을 한눈에 거기 올려놓을 수 있어."

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

"입력을 거의 안 알아챔" 에서 "재채기만 해도 죽음" 순으로:

O(1) 상수 — dict 조회, 배열 인덱싱, 리스트 append. 꿈이야. 입력 크기가 무관해.
O(log n) 로그 — 이진 탐색, 균형 트리 조회. 매 단계 절반. 십억 개를 ~30 단계에.
O(n) 선형 — 리스트 훑기, 최댓값 찾기. 각 항목 한 번씩. 정직하고 괜찮아.
O(n log n) 선형로그 — 좋은 정렬들 (merge, 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!) — 화재 경보야: 작은 테스트 케이스에선 돌아가고 진짜 입력에서 폭발해. 알고리즘 설계의 큰 부분 (특히 Dynamic Programming 트랙) 은 지수 무차별 대입을 실제로 출시 가능한 다항식으로 끌어내리는 거야.

피파의 고백

한 번 "모든 조합 시도" 해법을 짰는데 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