Big-O — 성장률의 경주
여섯 복잡도(O(1)~O(2ⁿ))의 연산 수를 n이 커질 때마다 실계산해 로그 스케일 막대로 대비시키고, '같은 일을 몇 년 걸려 하는가'까지 환산한다.
1 / 9여섯 복잡도가 같은 출발선에 섭니다. n이 두 배가 될 때 연산 수가 어떻게 자라는지 — 막대의 '기울기'가 알고리즘의 운명입니다.
입력 크기 n = 1 · 막대는 log 스케일 (선형이면 지수가 화면을 뚫습니다)
O(1)1회
O(log n)1회
O(n)1회
O(n log n)1회
O(n²)1회
O(2ⁿ)2회
단계 목록 · 키보드 ←/→ 이동, Space 재생
Big-O는 '빠르냐'가 아니라 'n이 두 배가 될 때 얼마나 더 일하느냐'다 — 작은 n에서는 상수가 이기지만, n이 자라면 성장률이 전부를 결정한다.
왜 헷갈리는가
"O(1)이 O(n)보다 항상 빠르다"가 대표 오해다. 상수가 크면 작은 n에서 O(n)이 이긴다 — 그래서 퀵 정렬 구현들이 작은 구간에서 삽입 정렬로 갈아탄다. Big-O는 벤치마크가 아니라 확장성의 언어다.
애니메이션이 보여주는 것
n≤4에서는 여섯 막대가 다 비슷하다 — 복잡도는 작은 입력에서 보이지 않는다. n=16부터 O(2ⁿ)이 폭주하고, n=32에서는 O(log n)과의 격차가 8억 배를 넘는다. 막대가 로그 스케일인 이유: 선형이면 지수가 화면을 뚫는다.
마지막 환산이 급소다 — 초당 1억 연산 기계로 n=40의 2ⁿ은 3시간, n=60이면 365년. 하드웨어 10배는 지수 앞에서 n을 3~4 늘려 줄 뿐이다. 알고리즘 교체만이 답인 영역이 존재한다.
실무 감각
복잡도를 다루는 현장의 습관.
- n의 규모부터 묻는다: n≤1,000이면 O(n²)도 순식간 — 단순한 코드가 이긴다. n이 백만이면 O(n log n)이 마지노선.
- 숨은 곱을 조심: 루프 안의 includes/indexOf(O(n))가 O(n²)를 만든다 — 배열을 Set으로 바꾸는 것이 가장 흔한 한 줄 최적화.
- 평균과 최악: 해시맵 O(1)은 평균이고, 퀵 정렬 O(n log n)도 평균이다 — 최악(O(n), O(n²))이 문제 되는 자리(적대적 입력, 실시간 보장)인지 확인.
- 공간도 같은 언어: 시간을 사려고 공간을 내는(메모이제이션) 거래가 Big-O의 절반이다.
기억할 것
- Big-O = 성장률. 작은 n의 승부는 상수가, 큰 n의 승부는 성장률이 정한다.
- 지수(2ⁿ)는 하드웨어로 못 이긴다 — 알고리즘 교체의 영역.
- 루프 속 O(n) 연산이 만드는 숨은 O(n²)가 실무 성능 사고의 단골.
- n의 규모를 먼저 물어라 — 그것이 Big-O를 쓰는 법이다.