Big O — 알고리즘의 성능 표기
Big O — 알고리즘의 성능 표기
"이 코드는 빠른가요" 라는 물음은 환경 · 하드웨어 · 입력에 따라 답이 달라집니다. 그래서 컴퓨터 과학은 입력 크기가 커질 때 시간 (또는 메모리) 이 어떻게 자라는지를 함수 형태로 표기. 그 표기가 Big O. 이 글은 Big O 의 출자 · 자주 만나는 성장률 · 시간과 공간 복잡도 · 실무에서의 의미와 한계.
1. Big O 에 대한 이야기
표기는 1894 년 독일 수학자 Paul Bachmann 의 저서 Analytische Zahlentheorie 에 처음 등장했고, 1909 년 Edmund Landau 가 정리해 "Landau symbols" 로도 불림. 컴퓨터 과학에서는 1976 년 Donald Knuth 의 논문 "Big Omicron and big Omega and big Theta" 가 표기 관습을 정착.
자매 표기:
| 표기 | 의미 |
|---|---|
O(f) |
상한 — 적어도 이만큼은 빠름 (실제 수행이 c·f(n) 이하) |
Ω(f) |
하한 — 적어도 이만큼은 느림 |
Θ(f) |
정확한 차수 — 상한과 하한이 같음 |
o(f) |
엄격한 상한 — 실제로 더 빠름 |
일상 대화에서는 거의 모두 Big O 로 부르고, 의도가 정확한 차수면 Θ 와 같이 해석.
2. 자주 만나는 성장률
| 표기 | 이름 | 입력 1 만 → 100 만 일 때 |
|---|---|---|
| O(1) | 상수 | 그대로 |
| O(log n) | 로그 | 약 1.3배 |
| O(n) | 선형 | 100배 |
| O(n log n) | 선형로그 | 약 130배 |
| O(n²) | 이차 | 1만배 |
| O(n³) | 삼차 | 100만배 |
| O(2ⁿ) | 지수 | 사실상 영원 |
| O(n!) | 팩토리얼 | 사실상 영원 |
같은 자료에 같은 작업을 해도 알고리즘 선택에 따라 100 만 배 차이가 난다는 의미.
3. 그래프
시간
│ O(2ⁿ)
│ O(n²)
│ ╱
│ ╱
│ ╱
│ ╱ O(n log n)
│ ╱ O(n)
│ ╱ ────
│ ╱ ────
│──── O(log n)
│═══════════════════════════ O(1)
└───────────────────────────── → 입력 크기 n
4. 상수 무시
Big O 는 입력이 충분히 커졌을 때의 양상을 봅니다. 상수 배수와 낮은 차수 항은 무시:
3n + 5 → O(n)
n² + n + 7 → O(n²)
1000n → O(n)
0.001 · 2ⁿ → O(2ⁿ)
이 단순화 덕에 대화가 짧아지지만, 실무에서는 상수가 의미를 가질 때가 있음. "O(n) 인데 상수가 1000" 과 "O(n log n) 인데 상수가 1" 은 작은 입력에서 후자가 더 빠를 수 있음.
5. 최선 · 평균 · 최악
같은 알고리즘이라도 입력에 따라 시간이 다름:
| 알고리즘 | 최선 | 평균 | 최악 |
|---|---|---|---|
| 선형 검색 | O(1) | O(n) | O(n) |
| 이진 검색 (정렬됨) | O(1) | O(log n) | O(log n) |
| 퀵 정렬 | O(n log n) | O(n log n) | O(n²) — 이미 정렬된 입력 등 |
| 머지 정렬 | O(n log n) | O(n log n) | O(n log n) |
| 해시 테이블 조회 | O(1) | O(1) | O(n) — 충돌 폭증 |
운영에서는 평균보다 최악 을 보고 결정하는 경우가 많음. 사용자 한 명이라도 최악을 만나면 화면이 멎기 때문.
6. 공간 복잡도
시간 외에 메모리가 입력에 따라 어떻게 자라는지도 같은 표기로. 재귀가 깊으면 호출 스택 메모리가 같이 자라므로 시간만 보고 결정하면 OOM:
| 알고리즘 | 시간 | 공간 |
|---|---|---|
| 머지 정렬 | O(n log n) | O(n) — 보조 배열 |
| 퀵 정렬 (in-place) | O(n log n) | O(log n) — 콜스택 |
| 동적 프로그래밍 | 다양 | O(n) ~ O(n²) — 메모이제이션 표 |
| 메모리 효율 정렬 (heap sort) | O(n log n) | O(1) |
7. 다른 길
성능을 표현하는 다른 단위:
- Wall-clock time — 실제 걸린 시간 (초). 환경에 좌우.
- CPU time — CPU 점유 시간.
- 연산 횟수 — 비교 횟수 · 메모리 접근 횟수.
- 벤치마크 — 같은 환경에서 두 구현을 비교.
이론과 실측의 거리가 자주 문제. CPU 캐시 · 분기 예측 · SIMD · 메모리 지역성이 Big O 가 못 잡는 자리에서 큰 차이. 운영 자리는 결국 측정해서 결정.
8. 코드를 보고 Big O 추정
// O(1) — 입력에 무관
function first(arr) { return arr[0]; }
// O(n) — 한 번 순회
function sum(arr) {
let s = 0;
for (const x of arr) s += x;
return s;
}
// O(n²) — 이중 루프
function pairs(arr) {
const out = [];
for (let i = 0; i < arr.length; i++) {
for (let j = i + 1; j < arr.length; j++) {
out.push([arr[i], arr[j]]);
}
}
return out;
}
// O(log n) — 매번 절반으로 줄임
function binarySearch(sorted, target) {
let lo = 0, hi = sorted.length - 1;
while (lo <= hi) {
const mid = Math.floor((lo + hi) / 2);
if (sorted[mid] === target) return mid;
if (sorted[mid] < target) lo = mid + 1;
else hi = mid - 1;
}
return -1;
}
// O(n log n) — 정렬 + 한 번 순회
function uniqueSorted(arr) {
return [...new Set(arr)].sort();
}
자주 쓰는 휴리스틱:
- 단순 한 번 루프 → O(n)
- 중첩 루프 → 깊이의 곱. 두 번이면 O(n²)
- 반복마다 절반으로 줄어드는 구조 → O(log n)
- 정렬을 한 번 하고 그 위에서 작업 → O(n log n)
- 모든 부분집합 → O(2ⁿ)
- 모든 순열 → O(n!)
9. 자주 걸리는 자리
근거 없는 최적화 — Knuth 의 1974 년 글 "premature optimization is the root of all evil" 이 자주 인용. 측정 없이 미리 비비 꼬는 일을 경계.
상수의 함정 — O(n) 인데 한 번의 단계가 매우 비싸면 (디스크 I / O) 같은 차수의 다른 알고리즘에 밀림.
작은 입력 vs 큰 입력 — n 이 100 정도면 어떤 차수든 비슷. n 이 100 만이 되어야 차이가 도드라짐.
메모리 우선 — 캐시 친화적인 O(n²) 가 캐시 비친화적인 O(n log n) 보다 작은 ~ 중간 입력에서 빠를 수 있음.
분할 상환 (amortized) 무시 — 동적 배열의 push 는 가끔 O(n) 이지만 평균 O(1). amortized 라고 부름. 한 번의 비싸짐을 보고 "느린 자료구조" 라 단정하면 잘못.
이론 vs 실측의 차이 — 비슷한 차수면 측정으로 결정하는 편이 정직.
하고픈 말
Big O 는 입력이 커질 때의 양상을 한 줄로 묘사하는 도구. 일상의 자료구조 선택은 이 표기 한 줄로 거의 답이 결정됨. 단 운영의 결정은 결국 측정으로 — 이론과 실측이 어긋나는 자리가 많기 때문. "premature optimization is the root of all evil" 의 인용이 여기서 살아 있는 자리.
Next
- design-patterns
- oop-vs-functional
Donald Knuth Big Omicron and big Omega and big Theta (1976) · The Art of Computer Programming · Knuth Structured Programming with go to Statements (1974) · Introduction to Algorithms (CLRS) · MIT 6.006 · Big-O Cheat Sheet · VisuAlgo · Wikipedia Big O notation 을 참고합니다.