시간 복잡도와 공간 복잡도 — O(n)이 뭔지 진짜로 아시나요
"이 알고리즘의 시간 복잡도가 어떻게 되나요?"라는 질문에 O(n)이라고 답하는 건 쉽습니다. 그런데 "왜 O(n log n)이에요?"라고 물으면 어떤가요?
코딩 테스트에서 시간 초과가 나는 이유, 알고리즘을 고르는 기준 — 이 모든 판단의 출발점이 복잡도입니다. 외우는 게 아니라 왜 그런 증가율이 나오는지 이해해야 합니다.
개념 정의
Big-O 표기법 은 입력 크기(n)가 커질 때 연산 횟수의 증가 추세 를 나타내는 표기법입니다. 정확한 연산 횟수가 아니라 "n이 충분히 커졌을 때 어떤 항이 지배적인가"를 봅니다.
아래 예시로 핵심을 짚어보겠습니다.
f(n) = 3n² + 5n + 100
n이 작으면 100이 지배적
n이 커지면 3n²이 지배적
→ O(n²)
3n²에서 계수 3은 무시합니다 — n이 충분히 크면 계수는 증가율에 영향을 주지 않기 때문입니다.5n과100도 무시합니다 — 최고차항에 비해 증가 속도가 무의미하기 때문입니다.- 결과적으로 가장 빠르게 증가하는 항 만 남깁니다.
흔한 복잡도 비교
느린 쪽부터:
| 복잡도 | 이름 | n=1,000일 때 | 예시 |
|---|---|---|---|
| O(1) | 상수 | 1 | 배열 인덱스 접근, HashMap get |
| O(log n) | 로그 | ~10 | 이진 탐색 |
| O(n) | 선형 | 1,000 | 배열 순회 |
| O(n log n) | 선형 로그 | ~10,000 | 퀵 정렬, 머지 정렬 |
| O(n²) | 이차 | 1,000,000 | 이중 for문, 버블 정렬 |
| O(2ⁿ) | 지수 | 10^301 | 부분집합 나열 |
| O(n!) | 팩토리얼 | ... | 순열 나열 |
O(n²) 이상은 n이 10,000만 넘어가도 실용적이지 않습니다. 코딩 테스트에서 시간 초과가 나는 대부분의 이유가 여기 있습니다.
실전에서 쓰는 감각
코딩 테스트에서 시간 제한은 보통 1~2초입니다. 1초에 약 1억 번 의 단순 연산이 가능하다고 봅니다.
| n의 범위 | 허용 가능한 복잡도 |
|---|---|
| n ≤ 10 | O(n!), O(2ⁿ) |
| n ≤ 20 | O(2ⁿ) |
| n ≤ 500 | O(n³) |
| n ≤ 5,000 | O(n²) |
| n ≤ 100,000 | O(n log n) |
| n ≤ 10,000,000 | O(n) |
| 그 이상 | O(log n), O(1) |
문제의 n 범위를 보고 알고리즘을 고르는 겁니다. n이 100,000인데 O(n²) 풀이를 떠올렸다면, 더 나은 방법을 찾아야 합니다.
왜 O(log n)이 나오는가
이진 탐색을 예로 들겠습니다. 핵심은 매 단계에서 탐색 범위가 절반으로 줄어든다 는 것입니다.
16개 → 8개 → 4개 → 2개 → 1개
매번 절반으로 줄어듦 → log₂(16) = 4번
- 16개의 요소에서 시작하면, 한 번 비교할 때마다 절반을 버립니다.
- 남은 요소가 1개가 될 때까지 반복하면, 총 비교 횟수는 log₂(n)입니다.
- 따라서 매 단계에서 문제 크기가 절반으로 줄어드는 알고리즘 은 O(log n)입니다.
왜 O(n log n)이 나오는가
머지 정렬을 예로 보겠습니다.
분할: log n 단계로 쪼갬
병합: 각 단계에서 n개 요소를 비교·이동
총: O(n) × O(log n) = O(n log n)
- 배열을 반으로 나누는 분할 과정이 log n 단계입니다 — 매번 절반이 되니까요.
- 각 단계에서 전체 n개 요소를 한 번씩 처리(병합)합니다.
- 결과적으로 "n개 요소 × log n 단계"가 되어 O(n log n)입니다.
최선/평균/최악
같은 알고리즘이라도 입력에 따라 성능이 달라질 수 있습니다.
| 최선 | 평균 | 최악 | |
|---|---|---|---|
| 퀵 정렬 | O(n log n) | O(n log n) | O(n²) |
| 삽입 정렬 | O(n) | O(n²) | O(n²) |
퀵 정렬은 평균적으로 빠르지만, 피벗이 편향되면 최악 O(n²)까지 떨어집니다. 반면 삽입 정렬은 이미 정렬된 배열에서는 O(n)으로 동작합니다. ** 어떤 입력에서 최악이 발생하는지** 파악하는 것이 중요합니다.
공간 복잡도
시간뿐 아니라 ** 추가로 사용하는 메모리 **도 분석 대상입니다.
O(1) 공간 — 변수 몇 개만 사용하는 경우입니다.
int sum = 0;
for (int i = 0; i < n; i++) {
sum += arr[i];
}
O(n) 공간 — 입력 크기에 비례하는 추가 배열을 만드는 경우입니다.
int[] copy = new int[n];
for (int i = 0; i < n; i++) {
copy[i] = arr[i];
}
O(n) 공간 — 재귀 호출 스택도 공간을 차지합니다.
void recursive(int n) {
if (n == 0) return;
recursive(n - 1); // 콜 스택에 n개의 프레임
}
재귀 깊이만큼 스택 프레임이 쌓이기 때문에, 깊이가 n이면 O(n) 공간입니다. 이 부분을 간과하고 "변수만 세면 O(1)이 아닌가?"라고 착각하는 경우가 잦습니다.
주의할 점
O(1)이 항상 O(n)보다 빠르지는 않다
Big-O는 상수를 무시합니다. O(1)이라도 내부 상수가 매우 크면(예: 연산 1억 번) 작은 n에서는 O(n)보다 느릴 수 있습니다.
- Big-O는 n이 충분히 클 때 의 증가 추세를 나타냅니다.
- 따라서 실제 실행 시간을 직접 비교하는 도구가 아닙니다.
- 작은 n에서의 성능은 상수 계수와 캐시 효율 등 다른 요인이 지배합니다.
재귀의 공간 복잡도를 빠뜨리는 실수
재귀 함수를 작성할 때 "추가 배열을 안 만들었으니 O(1)"이라고 생각하기 쉽습니다. 하지만 재귀 깊이만큼 콜 스택 프레임이 쌓이므로, 깊이가 n이면 O(n) 공간 입니다. 꼬리 재귀 최적화를 지원하지 않는 언어(Java 등)에서는 이 문제가 더 두드러집니다.
HashMap get()이 O(1)이 아닌 경우
해시 충돌이 극단적으로 발생하여 모든 키가 같은 버킷에 들어가면, 체이닝된 리스트를 순회해야 하므로 O(n)입니다. Java 8 이후에는 하나의 버킷에 8개 이상 쌓이면 레드-블랙 트리로 전환(Treeify)되어 O(log n)으로 개선됩니다.
O, Θ, Ω의 차이
| 표기 | 의미 |
|---|---|
| O (Big-O) | 상한 — 이것보다 나쁘진 않음 |
| Ω (Big-Omega) | ** 하한** — 이것보다 좋진 않음 |
| Θ (Big-Theta) | ** 정확한 차수** — 상한과 하한이 같음 |
일상적으로 O(n)이라고 하면 보통 Θ(n)의 의미로 쓰는 경우가 많습니다. 엄밀히 따지면 O(n)인 알고리즘은 O(n²)이기도 합니다(상한이니까). 실무에서 이 정도까지 구분하는 경우는 드뭅니다.
정리
| 항목 | 핵심 |
|---|---|
| Big-O란 | 입력 크기 n이 커질 때 연산 횟수의 증가 추세 |
| 상수/계수 무시 | 3n² + 5n + 100 → O(n²) |
| O(log n) | 매 단계에서 문제 크기가 절반으로 줄어드는 경우 |
| O(n log n) | n개 요소 × log n 단계 (머지 정렬 등) |
| 공간 복잡도 | 추가 메모리 + 재귀 콜 스택까지 포함 |
| n 범위 감각 | n ≤ 100,000이면 O(n log n) 이하 필요 |
| Big-O ≠ 실행 시간 | 상수가 큰 O(1)은 작은 n에서 O(n)보다 느릴 수 있음 |
파생되는 개념들
- ** 분할 상환 분석 (Amortized Analysis)** — ArrayList의 add()가 왜 O(1)인지
- ** 정렬 알고리즘 비교** — O(n log n)의 하한 증명
- ** 재귀와 점화식** — 시간 복잡도를 수학적으로 구하는 방법
- ** 마스터 정리 (Master Theorem)** — 분할 정복 알고리즘의 복잡도 계산