시간 복잡도와 공간 복잡도 완전 정복 — Big-O 표기법부터 실전 분석까지
전체 보기접기
시간 복잡도와 공간 복잡도, 왜 알아야 하나요?
- 같은 결과를 내는 코드가 두 개 있는데, 하나는 입력 10만 건에 0.1초, 다른 하나는 10분이 걸립니다
- "느리다"는 느낌만으로는 왜 느린지, 입력이 더 커지면 얼마나 나빠질지 말할 수 없습니다
- 면접에서도, 코드 리뷰에서도, 설계 단계에서도 **"이 알고리즘이 입력 크기에 따라 얼마나 느려지는가"**를 공유할 공통 언어가 필요합니다
시간 복잡도와 공간 복잡도는 알고리즘이 소비하는 시간과 메모리가 입력 크기에 따라 어떻게 증가하는지를 표현하는 도구입니다. 이 글에서는 Big-O 표기법의 정의부터, 대표적인 복잡도 등급, 공간 복잡도의 개념, 그리고 실전에서 복잡도를 분석하는 패턴까지 정리합니다.
Phase 1. Big-O 표기법 — 증가 속도를 표현하는 방법
정의
Big-O는 입력 크기 n이 충분히 커졌을 때, 알고리즘의 연산 횟수(또는 메모리 사용량)가 최대 얼마나 빠르게 증가하는지를 나타냅니다.
함수
f(n)에 대해f(n) = O(g(n))이란, 충분히 큰n에서f(n) ≤ c · g(n)을 만족하는 양의 상수c와n₀가 존재한다는 뜻입니다.
쉽게 말하면, 입력이 커질 때 연산 횟수가 g(n)보다 빠르게 늘어나지 않는다는 의미입니다.
왜 상수와 낮은 차수 항을 버리나요?
어떤 알고리즘이 정확히 3n² + 5n + 10번 연산한다고 합시다.
n |
3n² |
5n |
10 |
합계 | n² 항 비율 |
|---|---|---|---|---|---|
| 10 | 300 | 50 | 10 | 360 | 83% |
| 100 | 30,000 | 500 | 10 | 30,510 | 98% |
| 10,000 | 300,000,000 | 50,000 | 10 | 300,050,010 | 99.98% |
n이 커질수록 n² 항이 전체를 지배합니다. 상수 3이나 5n, 10은 증가 추세에 영향을 주지 않습니다. 그래서 3n² + 5n + 10 = O(n²)으로 표기합니다.
Big-O는 "정확한 연산 횟수"가 아니라 "증가 속도의 등급"을 비교하는 도구입니다.
Big-O, Big-Ω, Big-Θ
Big-O만으로는 상한만 알 수 있습니다. 실제로는 세 가지 표기가 있습니다.
| 표기 | 의미 | 비유 |
|---|---|---|
O(g(n)) |
최악의 경우에도 g(n) 이하 (상한) |
"아무리 느려도 이 정도" |
Ω(g(n)) |
최선의 경우에도 g(n) 이상 (하한) |
"아무리 빨라도 이 정도" |
Θ(g(n)) |
상한과 하한이 같은 등급 (정확한 등급) | "정확히 이 등급" |
실무와 면접에서는 대부분 최악의 경우 상한인 Big-O를 기준으로 이야기합니다. 이 글에서도 Big-O를 기본으로 사용합니다.
참고:
Big-O를 "최악의 경우"와 혼동하기 쉽지만, 엄밀히 다릅니다.Big-O는 수학적 상한 표기이고, "최악의 경우"는 입력 조건입니다. 예를 들어, 퀵소트의 평균 시간 복잡도는O(n log n)이고, 최악 시간 복잡도는O(n²)입니다. 둘 다Big-O로 표기하지만 기준 입력이 다릅니다.
Phase 2. 대표적인 시간 복잡도 — 느린 것부터 빠른 것까지
입력 크기 n에 따른 대표 복잡도를 빠른 순서로 정리합니다.
O(1) — 상수 시간
입력 크기와 관계없이 연산 횟수가 일정합니다.
fun getFirst(arr: IntArray): Int {
return arr[0]
}
배열 크기가 100이든 100만이든 한 번입니다. 배열 인덱스 접근, HashMap의 get/put(평균), 스택의 push/pop이 대표적입니다.
O(log n) — 로그 시간
한 단계마다 탐색 범위가 절반으로 줄어듭니다.
fun binarySearch(arr: IntArray, target: Int): Int {
var lo = 0
var hi = arr.size - 1
while (lo <= hi) {
val mid = (lo + hi) / 2
when {
arr[mid] == target -> return mid
arr[mid] < target -> lo = mid + 1
else -> hi = mid - 1
}
}
return -1
}
n = 1,000,000이어도 log₂(1,000,000) ≈ 20번이면 끝납니다. 이진 탐색, 균형 이진 탐색 트리의 조회가 대표적입니다.
O(n) — 선형 시간
입력 전체를 한 번 훑습니다.
fun sum(arr: IntArray): Int {
var total = 0
for (num in arr) {
total += num
}
return total
}
배열 전체 순회, LinkedList에서 특정 값 검색, 단순 집계가 여기에 해당합니다.
O(n log n) — 선형 로그 시간
전체를 훑되, 각 단계에서 분할이 일어나는 패턴입니다.
fun mergeSort(arr: IntArray): IntArray {
if (arr.size <= 1) return arr
val mid = arr.size / 2
val left = mergeSort(arr.sliceArray(0 until mid))
val right = mergeSort(arr.sliceArray(mid until arr.size))
return merge(left, right)
}
배열을 반씩 나누는 단계가 log n번, 각 단계에서 n개를 합치므로 O(n log n)입니다. 머지 소트, 힙 소트, 퀵소트(평균)가 대표적입니다.
참고: 비교 기반 정렬의 이론적 하한은
Ω(n log n)입니다. 비교만으로는 이보다 빠르게 정렬할 수 없다는 뜻입니다.
O(n²) — 이차 시간
이중 반복문이 대표적입니다.
fun bubbleSort(arr: IntArray) {
val n = arr.size
for (i in 0 until n) {
for (j in 0 until n - 1 - i) {
if (arr[j] > arr[j + 1]) {
val temp = arr[j]
arr[j] = arr[j + 1]
arr[j + 1] = temp
}
}
}
}
모든 쌍을 비교하는 버블 정렬, 선택 정렬, 삽입 정렬(최악)이 여기에 해당합니다. n = 10,000이면 약 10^8번 연산이며, 이 근처부터 체감 속도가 급격히 느려집니다.
O(2^n) — 지수 시간
입력이 하나 늘 때마다 연산량이 두 배가 됩니다.
fun fibonacci(n: Int): Int {
if (n <= 1) return n
return fibonacci(n - 1) + fibonacci(n - 2)
}
위 코드에서 fibonacci(50)은 호출 횟수가 약 2^50 ≈ 10^15에 달합니다. 메모이제이션 없이는 현실적으로 불가능합니다. 부분 집합 열거, 일부 백트래킹 문제가 이 범주에 들어갑니다.
O(n!) — 팩토리얼 시간
모든 순열을 시도하는 경우입니다.
fun permutations(arr: IntArray, start: Int = 0) {
if (start == arr.size - 1) {
// 하나의 순열 처리
return
}
for (i in start until arr.size) {
arr[start] = arr[i].also { arr[i] = arr[start] }
permutations(arr, start + 1)
arr[start] = arr[i].also { arr[i] = arr[start] }
}
}
n = 20이면 20! ≈ 2.4 × 10^18입니다. 외판원 문제(TSP)의 브루트포스가 대표적입니다.
증가 속도 비교
n이 커질수록 등급 간 차이가 극적으로 벌어집니다.
n |
O(1) |
O(log n) |
O(n) |
O(n log n) |
O(n²) |
O(2^n) |
|---|---|---|---|---|---|---|
| 10 | 1 | 3 | 10 | 33 | 100 | 1,024 |
| 100 | 1 | 7 | 100 | 664 | 10,000 | 1.27 × 10³⁰ |
| 1,000 | 1 | 10 | 1,000 | 9,966 | 1,000,000 | — |
| 100,000 | 1 | 17 | 100,000 | 1,660,964 | 10¹⁰ | — |
O(n²)까지는 n이 수만 이하면 실용적이지만, O(2^n) 이상은 n = 30~40만 넘어도 현실적으로 불가능합니다.
Phase 3. 공간 복잡도 — 메모리도 자원이다
공간 복잡도란
시간 복잡도가 "연산 횟수의 증가 속도"라면, 공간 복잡도는 **"추가로 사용하는 메모리의 증가 속도"**입니다. 입력 자체를 저장하는 공간은 제외하고, 알고리즘이 추가로 할당하는 메모리만 셉니다. 이 추가 메모리를 **보조 공간(auxiliary space)**이라고 부릅니다.
O(1) 공간 — 변수 몇 개
fun findMax(arr: IntArray): Int {
var max = arr[0]
for (num in arr) {
if (num > max) max = num
}
return max
}
max 변수 하나만 추가로 사용합니다. 배열 크기가 커져도 추가 메모리는 일정하므로 O(1)입니다. 이런 알고리즘을 제자리(in-place) 알고리즘이라고 합니다.
O(n) 공간 — 입력 크기에 비례하는 자료 구조
fun twoSum(nums: IntArray, target: Int): IntArray {
val map = HashMap<Int, Int>()
for ((i, num) in nums.withIndex()) {
val complement = target - num
if (map.containsKey(complement)) {
return intArrayOf(map[complement]!!, i)
}
map[num] = i
}
return intArrayOf()
}
HashMap에 최대 n개의 원소가 들어가므로 O(n) 공간입니다.
재귀의 공간 복잡도 — 콜 스택도 메모리다
재귀 호출은 콜 스택에 프레임을 쌓습니다. 최대 재귀 깊이가 곧 공간 복잡도에 포함됩니다.
fun factorial(n: Int): Long {
if (n <= 1) return 1
return n * factorial(n - 1)
}
factorial(10000)은 콜 스택에 10,000개의 프레임이 쌓입니다. 공간 복잡도는 O(n)입니다.
이진 탐색의 재귀 버전은 최대 log n 깊이까지 내려가므로 O(log n) 공간입니다. 반복문 버전은 콜 스택을 쓰지 않아 O(1)입니다. 같은 알고리즘이라도 구현 방식에 따라 공간 복잡도가 달라질 수 있습니다.
시간-공간 트레이드오프
시간을 줄이려면 메모리를 더 쓰고, 메모리를 아끼려면 시간이 더 드는 경우가 많습니다.
| 문제 | 시간 우선 (시간 / 공간) | 공간 우선 (시간 / 공간) |
|---|---|---|
| 중복 원소 찾기 | HashSet 탐색: O(n) / O(n) |
정렬 후 인접 비교: O(n log n) / O(1) |
| 피보나치 | 메모이제이션: O(n) / O(n) |
변수 두 개로 반복: O(n) / O(1) |
| Two Sum | HashMap: O(n) / O(n) |
이중 반복: O(n²) / O(1) |
어떤 쪽이 정답인지는 제약 조건에 따라 다릅니다. 메모리가 넉넉하면 시간을 줄이는 쪽이 유리하고, 메모리 제한이 빡빡하면 공간을 아끼는 풀이가 필요합니다. Increasing Triplet Subsequence 풀이에서 O(n) / O(n) 풀이를 O(n) / O(1)로 줄여 나가는 과정이 이 트레이드오프의 좋은 예시입니다.
Phase 4. 실전에서 복잡도를 분석하는 패턴
패턴 1: 단순 반복문
for (i in 0 until n) {
// O(1) 작업
}
O(n)입니다. 반복 횟수가 곧 시간 복잡도입니다.
패턴 2: 중첩 반복문
for (i in 0 until n) {
for (j in 0 until n) {
// O(1) 작업
}
}
바깥 n × 안쪽 n = O(n²)입니다. 안쪽 루프가 m번이면 O(n × m)입니다.
패턴 3: 반씩 줄어드는 반복
var x = n
while (x > 0) {
x /= 2
}
n → n/2 → n/4 → ... → 1이므로 O(log n)입니다.
패턴 4: 분할 정복 재귀
fun solve(arr: IntArray, lo: Int, hi: Int) {
if (lo >= hi) return
val mid = (lo + hi) / 2
solve(arr, lo, mid)
solve(arr, mid + 1, hi)
merge(arr, lo, mid, hi) // O(n) 작업
}
각 레벨에서 총 O(n) 작업, 레벨 수 O(log n) → O(n log n)입니다.
참고: 이 형태는 **마스터 정리(Master Theorem)**로 일반화할 수 있습니다.
T(n) = aT(n/b) + O(n^d)형태의 재귀식에서a,b,d의 관계로 복잡도를 바로 결정합니다. 위 예시는a = 2, b = 2, d = 1이고,a = b^d이므로O(n^d · log n) = O(n log n)입니다.
패턴 5: 재귀 호출이 여러 갈래로 폭발하는 경우
fun fib(n: Int): Int {
if (n <= 1) return n
return fib(n - 1) + fib(n - 2)
}
매 호출마다 두 갈래로 분기하고, 깊이는 n입니다. 호출 트리의 노드 수는 O(2^n)입니다.
복잡도 판단 체크리스트
코드를 읽을 때 다음 질문을 던져 보면 복잡도를 빠르게 잡을 수 있습니다.
- 반복문이 몇 겹인가? — 1겹
O(n), 2겹O(n²), 3겹O(n³) - 반복마다 범위가 절반으로 줄어드는가? —
O(log n) - 재귀가 있다면, 한 호출에서 몇 개의 하위 호출이 생기는가? — 1개면
O(n)또는O(log n), 2개 이상이면 지수 가능성 - 자료 구조를 새로 만드는가? — 만든다면 그 크기가 공간 복잡도
- 정렬, 탐색 등 내장 함수를 쓰는가? — 내장 정렬은 보통
O(n log n),HashMap조회는 평균O(1)
마무리
| 복잡도 | 대표 패턴 | n = 10^6일 때 체감 |
|---|---|---|
O(1) |
인덱스 접근, 해시 조회 | 즉시 |
O(log n) |
이진 탐색, 균형 트리 | 약 20회 |
O(n) |
단순 순회, 선형 탐색 | 현실적 |
O(n log n) |
효율적 정렬, 분할 정복 | 현실적 |
O(n²) |
이중 반복, 단순 정렬 | 약 10¹² — 느림 |
O(2^n) |
부분 집합, 메모이제이션 없는 재귀 | 사실상 불가능 |
Big-O는 "정확한 연산 횟수"가 아니라 "입력이 커질 때의 증가 등급" — 상수와 낮은 차수 항을 버려도 알고리즘 간 비교에는 충분합니다- 공간 복잡도는 "추가 메모리"만 센다 — 입력 자체가 아니라, 알고리즘이 동작하면서 할당하는 자료 구조와 콜 스택이 대상입니다
- 시간과 공간은 트레이드오프 관계인 경우가 많다 —
HashMap으로 시간을 줄이면 공간이 늘고, 정렬 후 순회하면 공간은 줄지만 시간이 더 듭니다 - 복잡도 분석의 핵심은 "반복문 겹 수"와 "범위가 줄어드는 속도" — 이 두 가지를 먼저 보면 대부분의 코드에서 복잡도를 빠르게 잡을 수 있습니다
Can Place Flowers — `O(n)` 그리디 스캔으로 인접 금지 배치 판정
다음 편Greatest Common Divisor of Strings — `GCD`로 `O(n + m)` 문자열 최대 공약 패턴
다음으로 읽어볼 글
Greatest Common Divisor of Strings — `GCD`로 `O(n + m)` 문자열 최대 공약 패턴
두 문자열의 최대 공약 문자열을 구하는 LeetCode 1071번, 브루트포스부터 GCD 기반 O(n + m) 풀이까지 정리합니다.
Can Place Flowers — `O(n)` 그리디 스캔으로 인접 금지 배치 판정
인접한 화단에 꽃을 동시에 심을 수 없을 때 `n`송이 배치가 가능한지 판단하는 LeetCode 605번, 그리디 선택이 왜 최적인지와 배열 수정 없이 `O(n)`/`O(1)`로 푸는 방법을 정리합니다.
Increasing Triplet Subsequence — `O(n)` 시간, `O(1)` 공간으로 푸는 그리디 패턴
삼중 반복 `O(n^3)`부터, `leftMin`/`rightMax` 두 배열을 쓰는 `O(n)`/`O(n)`, 그리고 변수 두 개로 `O(n)`/`O(1)`에 푸는 그리디까지, `first`/`second` 불변식을 기준으로 정리합니다.