시간 복잡도: 자료가 늘면 얼마나 느려지나(빅오)
코드가 칸 10개에서는 빨랐는데 100만 개에서는 멈춘 듯합니다. 왜 그런지는 「자료가 두 배가 되면 걸음이 몇 배가 되나」로 설명됩니다. n 을 움직이며 여섯 가지 모양을 비교하고, 값 찾기의 걸음을 직접 세어 보세요.
한 줄 답. 시간 복잡도(time complexity)는 자료의 수 n 이 늘 때 연산 횟수가 어떤 모양으로 늘어나나입니다. 초가 아닙니다. 빅오 표기(Big O notation, O(…))로 적고, 상수와 작은 항은 버립니다. O(n) 은 n 이 두 배면 두 배, O(n²) 은 네 배, O(log n) 은 한 걸음만 더입니다. 그래서 n 이 커지면 모양의 차이가 기계의 빠르기 차이를 이깁니다.
| 모양 | n 이 두 배가 되면 | 이런 일 | 지금 n 의 연산 횟수 |
|---|---|---|---|
| O(1) | 그대로 | 리스트의 k 번째 칸 읽기 | |
| O(log n) | 한 걸음 더 | 정렬된 칸에서 반씩 잘라 찾기(이진 탐색, binary search) | |
| O(n) | 두 배 | 앞에서부터 하나씩 찾기(선형 탐색, linear search) | |
| O(n log n) | 두 배보다 조금 더 | 정렬 | |
| O(n²) | 네 배 | 모든 둘씩 짝을 비교하기(for 안에 for) | |
| O(2ⁿ) | n 이 하나만 늘어도 두 배 | 모든 부분집합 훑기 |
그림 읽기: 가로는 1 부터 2n 까지입니다. 세로 점선이 지금 n 이고, 그 왼쪽 숫자가 지금 n 의 연산 횟수입니다. 굽은 화살표는 n 이 2n 으로 두 배가 될 때이고, 화살표 위의 ×2·×4 는 몇 배, +1 은 몇 더입니다. 곡선 이름은 색과 함께 오른쪽 끝에, 위로 나간 곡선은 나간 자리에 「↑」로 적습니다.
막대나 숫자 칸으로 n 을 바꿔 보세요(2 ~ 1000). 연산 횟수는 식에 n 을 넣은 값이고, 0.1 에서 반올림했습니다(log₂n 은 n 이 2 의 거듭제곱이 아니면 정수가 아닙니다). 2ⁿ 은 n = 53 부터 「셀 수 없이 큼」으로 적습니다. 그보다 크면 이 쪽의 숫자로는 정수를 정확히 적을 수 없습니다.
해 볼 것. ① 처음 n = 8 에서 연산 횟수는 1, 3, 8, 24, 64, 256 입니다. 그림은 2n = 16 까지 그립니다. 점선(n = 8)에서 2ⁿ 은 벌써 위로 나갔고, n² 은 64 로 아직 안에 있다가 16 에 닿기 전에 위로 나갑니다. 화살표 이름표는 1 이 ×1, log₂n 이 +1, n 이 ×2, n·log₂n 이 ×2.7 이고, 위로 나간 n² 은 ×4, 2ⁿ 은 ×256 입니다. ② n 을 16 으로 두 배 하면 4, 16, 64, 256, 65,536 입니다. log₂n 은 하나 늘고(3 → 4), n 은 두 배, n² 은 네 배(64 → 256), 2ⁿ 은 제곱(256 → 65,536)이 됩니다. ③ n = 52 에서 2ⁿ 은 4,503,599,627,370,496 이고, 53 부터 셀 수 없이 큽니다. ④ n = 1000 이면 log₂n 은 10, n 은 1,000, n·log₂n 은 9,965.8, n² 은 1,000,000 입니다. 그림에서 1 과 log₂n 은 바닥에 붙고, n 도 바닥 가까이 내려갑니다.
1. 빅오가 재는 것: 초가 아니라 늘어나는 모양
실행 시간은 대략 한 걸음에 드는 시간 × 연산 횟수 입니다. 앞의 것은 기계, 언어, 캐시가 정합니다. 뒤의 것은 알고리즘과 자료의 수 n 이 정합니다. 시간 복잡도는 뒤의 것만 봅니다. 걸음은 칸 하나 읽기, 값 둘 비교하기처럼 한 번에 끝나는 일 하나입니다.
그래서 빅오는 초를 말하지 않습니다. 「n 이 두 배가 되면 걸음이 몇 배가 되나」를 말합니다. 열 배 빠른 컴퓨터로 바꿔도 O(n²) 인 코드는 n 이 두 배면 여전히 네 배 걸립니다. n 이 충분히 커지면 모양이 나쁜 쪽은 빠른 기계로도 따라잡지 못합니다. 위 실험의 n = 1000 에서 n² 은 n 의 1,000 배입니다.
책의 정의는 이렇습니다. n 이 충분히 클 때 f(n) 이 g(n) 의 어떤 상수 배를 넘지 않으면 f(n) = O(g(n)) 이라고 씁니다. 곧 빅오는 「이보다 빨리 늘지는 않는다」는 상한(upper bound)입니다. 보통은 그 가운데 가장 딱 맞는 모양을 적습니다.
2. 걸음을 실제로 세어 보기: 값 찾기 두 방법
작은 것부터 정렬된 칸 n 개(2, 4, 6, …, 2n)에서 값 하나를 찾습니다. 선형 탐색은 첫 칸부터 차례로 봅니다. 이진 탐색은 남은 범위의 가운데 칸을 보고, 찾는 값보다 작으면 왼쪽 절반을, 크면 오른쪽 절반을 버립니다. 정렬돼 있으니 버린 쪽에는 찾는 값이 있을 수 없습니다. 아래 실험은 두 방법을 실제로 돌리며 칸을 볼 때마다 한 걸음으로 셉니다.
칸이 넓으면 칸 안에 값을, 아래 띠 밑에 본 차례(1, 2, 3, …)를 적습니다. 칸이 좁아지면 본 칸만 칠합니다. 「없는 값」은 맨 뒤 값보다 1 큰 홀수입니다.
해 볼 것. ① 처음(8칸, 맨 뒤 값 16)은 선형 탐색 8 걸음, 이진 탐색 4 걸음입니다. 이진 탐색이 본 값은 8, 12, 14, 16 입니다(3절의 표). ② 「맨 앞 값」은 선형 탐색 1 걸음, 이진 탐색 3 걸음이고, 「가운데 값」(8)은 선형 탐색 4 걸음, 이진 탐색 1 걸음입니다. 최선의 경우는 방법마다 다릅니다. ③ n 을 500 으로 두고 맨 뒤 값을 찾으면 500 걸음과 9 걸음, 1000 으로 두 배 하면 1,000 걸음과 10 걸음입니다. 선형 탐색은 두 배, 이진 탐색은 한 걸음 더입니다. ④ 「없는 값」은 두 방법 모두 맨 뒤 값과 같은 걸음이 듭니다. 끝까지 봐야 없다는 것을 압니다.
3. 손으로 따라가기: 8칸에서 16 찾기
실험 ② 의 처음과 같은 입력입니다. 칸은 2, 4, 6, 8, 10, 12, 14, 16 이고 칸 번호는 0 부터 7 까지입니다. 찾는 값은 16 입니다.
선형 탐색. 2, 4, 6, 8, 10, 12, 14 를 보고 아니어서 넘어가고, 여덟째에 16 을 만납니다. 8 걸음입니다. 맨 뒤에 있으니 칸 수만큼 듭니다.
이진 탐색. 가운데 칸 번호는 (왼쪽 끝 + 오른쪽 끝) ÷ 2 를 내림한 것입니다.
| 걸음 | 남은 범위(칸 번호) | 가운데 칸 | 그 값 | 16 과 비교하면 | 다음 |
|---|---|---|---|---|---|
| 1 | 0 ~ 7 (8칸) | 3 | 8 | 작다(8 < 16). 정렬돼 있으니 16 은 오른쪽에만 있을 수 있다 | 0 ~ 3 을 버린다 → 4 ~ 7 |
| 2 | 4 ~ 7 (4칸) | 5 | 12 | 작다(12 < 16). 16 은 오른쪽에만 있을 수 있다 | 4 ~ 5 를 버린다 → 6 ~ 7 |
| 3 | 6 ~ 7 (2칸) | 6 | 14 | 작다(14 < 16). 16 은 오른쪽에만 있을 수 있다 | 6 을 버린다 → 7 ~ 7 |
| 4 | 7 ~ 7 (1칸) | 7 | 16 | 같다(16 = 16) | 찾았다 |
남은 칸이 8 → 4 → 2 → 1 로 반씩 줄었습니다. 8 을 1 이 될 때까지 반으로 자르는 횟수가 log₂8 = 3 이고, 마지막 한 칸을 보는 한 걸음을 더해 4 걸음입니다. 일반으로는 많아야 ⌊log₂n⌋ + 1 걸음입니다(⌊ ⌋ 는 내림). n = 1000 이면 10 걸음입니다. 칸이 두 배가 되면 반으로 자를 일이 한 번 늘 뿐이라서 O(log n) 입니다. 이 방법은 이진 탐색 쪽에서 더 자세히 봅니다.
4. 규칙: 상수와 작은 항을 버린다
| 규칙 | 예 | 까닭 |
|---|---|---|
| 상수 배는 버린다 | 3n → O(n) | 상수는 기계와 언어가 바꾸는 몫입니다. n 이 두 배일 때 몇 배가 되나는 상수와 상관없습니다 |
| 작은 항은 버린다 | n² + 100n → O(n²) | n = 1,000 이면 n² 은 1,000,000, 100n 은 100,000 입니다. n = 100,000 이면 10,000,000,000 대 10,000,000 으로, 작은 항이 0.1% 입니다. n 이 클수록 큰 항만 남습니다 |
| 차례로 하면 큰 쪽만 남는다 | 정렬(n log n) 뒤 한 번 훑기(n) → O(n log n) | 둘을 더하면 작은 쪽이 작은 항이 됩니다 |
| 안에 넣으면 곱한다 | n 번 도는 for 안에 n 번 도는 for → O(n²) | 바깥 한 바퀴마다 안쪽이 n 걸음입니다 |
| 로그의 밑은 적지 않는다 | log₂n 과 log₁₀n 은 둘 다 O(log n) | 밑을 바꾸면 상수 배만 달라집니다(log₂n ≈ 3.32 × log₁₀n) |
버리는 까닭은 하나입니다. 빅오는 n 이 커질 때 무엇이 이기는지 보려는 도구라서, n 이 커지면 어차피 묻히는 것을 들고 다니지 않습니다. 대신 n 이 작을 때는 버린 것이 크게 남을 수 있습니다(자주 묻는 것 1). Princeton 의 알고리즘 교재는 작은 항만 버리고 앞의 상수는 남기는 물결표 표기를 씁니다: 3n² + 100n ~ 3n². 빅오는 거기서 상수 3 까지 버린 것입니다.
5. 최악의 경우와 평균의 경우
같은 n 이라도 입력에 따라 연산 횟수가 다릅니다. 실험 ② 에서 본 것처럼 찾는 값이 어디 있느냐에 따라 1 걸음일 수도, n 걸음일 수도 있습니다. 그래서 어느 경우를 말하는지 같이 적습니다.
- 최악의 경우(worst case). 어떤 입력이 와도 이보다는 안 걸린다는 약속입니다. 선형 탐색은 n 걸음(맨 뒤 값이나 없는 값), 이진 탐색은
⌊log₂n⌋ + 1걸음입니다. 따로 말이 없으면 흔히 이것을 뜻합니다. 다만 Python 문서의 dict 처럼 보통의 값을 적는 곳도 있습니다. Princeton 교재는 원자로나 자동차 브레이크를 움직이는 소프트웨어처럼 늦으면 안 되는 곳에 이 약속이 맞다고 적습니다. - 평균의 경우(average case). 입력이 흔히 오는 모양일 때의 평균입니다. 찾는 값이 n 칸 어디에나 같은 확률로 있다면 선형 탐색은 평균
(1 + 2 + … + n) ÷ n = (n + 1) ÷ 2걸음이고, 여전히 O(n) 입니다. dict 찾기는 보통 O(1) 이지만 최악의 경우는 O(n) 입니다. - 최선의 경우(best case). 맨 앞 값이면 1 걸음입니다. 아무것도 약속해 주지 않아서 따로 쓰는 일은 드뭅니다.
- 분할 상환 분석. 리스트의
append처럼 가끔 비싼 한 번이 끼어도, 여러 번 한 전체를 횟수로 나누면 한 번에 O(1) 인 것이 있습니다. 이것을 분할 상환(amortized)이라고 부르고, 여러 번 한 전체에 대한 최악의 경우의 약속입니다.
6. 메모리도 같은 방식으로 잰다
메모리는 입력 말고 더 드는 칸이 n 에 따라 어떻게 늘어나나로 잽니다(공간 복잡도, space complexity). 규칙은 시간과 같습니다.
- 실험 ② 의 두 찾기는 칸 번호 몇 개만 들고 다닙니다. n 이 커져도 그대로라
O(1)입니다. sorted(a)는 정렬된 새 리스트를 만들어 n 칸이 더 듭니다:O(n).a.sort()는 같은 리스트를 고칩니다.- 점 n 개의 모든 쌍 거리를 표로 두면 n × n 칸:
O(n²). n = 100,000 이면 칸이 100억 개라 메모리에 들어가지 않습니다.
시간과 메모리는 서로 바꿀 수 있습니다. 리스트에서 값을 여러 번 찾을 일이 있으면 set 이나 dict 를 한 번 만들어 둡니다. 메모리가 n 칸 더 들지만 찾기가 O(n) 에서 보통 O(1) 로 줍니다. Princeton 교재는 메모리를 바이트로 셀 때 변수의 수에 그 종류가 쓰는 바이트를 곱해 더합니다(Java 기준).
7. 흔한 일의 연산 횟수: 언제 무엇을 쓰나
Python 문서(CPython 기준)에 적힌 값입니다. 쉬운 말은 실험 ① 의 표와 같습니다: O(1) 은 n 과 상관없음, O(log n) 은 두 배면 한 걸음 더, O(n) 은 두 배면 두 배.
| 하는 일 | Python | 최선의 경우 | 평균의 경우 | 최악의 경우 | 더 드는 메모리 | 언제 쓰나 |
|---|---|---|---|---|---|---|
| 리스트 맨 뒤에 넣기 | a.append(x) | O(1) | O(1) | 그 한 번은 O(n)(자리를 늘려 옮길 때), 나눠 내면 O(1) | 없음 | 쌓아 가는 일은 늘 이것 |
| 리스트 맨 앞에 넣기 | a.insert(0, x) | O(n) | O(n) | O(n) | 없음 | 뒤의 칸을 모두 한 칸씩 밉니다. 양 끝에 자주 넣고 빼면 collections.deque |
| 리스트에 값이 있나 | x in a | O(1) | O(n) | O(n) | 없음 | 한두 번이면 이것. 반복문 안에서 묻는다면 set 이나 dict 로 |
| 정렬된 칸에서 이진 탐색 | bisect.bisect_left(a, x) | O(log n) | O(log n) | O(log n) | 없음 | 이미 정렬돼 있고 순서도 필요할 때 |
| dict 에서 찾기 | d[k], k in d | O(1) | O(1) | O(n)(모든 키의 해시가 같을 때) | dict 자체가 n 칸 | 키로 여러 번 찾을 때 |
| 정렬 | sorted(a), a.sort() | O(n)(이미 정렬됐거나 거꾸로일 때의 비교 수) | O(n log n) | O(n log n) | sorted 는 새 리스트 n 칸 | 한 번 정렬해 두고 여러 번 찾을 때. 방법은 기초 정렬, 병합·퀵 정렬 |
실험 ② 의 이진 탐색은 가운데 값이면 1 걸음에 멈추지만, bisect_left 는 값이 같아도 멈추지 않고 들어갈 자리를 끝까지 좁혀서 늘 log n 쯤 걸립니다. dict 가 왜 보통 O(1) 인지는 해시 테이블 쪽에서 봅니다.
8. Python 으로
실험 ② 의 이진 탐색을 그대로 옮기고 걸음을 셉니다.
def binary_search(cells, target): # cells 는 작은 것부터 정렬돼 있다
low, high, steps = 0, len(cells) - 1, 0
while low <= high:
middle = (low + high) // 2 # 남은 범위의 가운데 칸
steps += 1
if cells[middle] == target:
return middle, steps
if cells[middle] < target:
low = middle + 1 # 왼쪽 절반을 버린다
else:
high = middle - 1 # 오른쪽 절반을 버린다
return -1, steps
cells = list(range(2, 2001, 2)) # 2, 4, ..., 2000 (1000칸)
print(binary_search(cells, 2000)) # (999, 10)
import bisect; print(bisect.bisect_left(cells, 2000)) # 999: 표준 라이브러리
어디에 쓰나
- 코드 리뷰. 반복문 안의
x in 리스트는 숨은 for 라서 전체가 O(n²) 입니다. set 으로 바꾸면 보통 O(n) 이 됩니다. - 자료 구조 고르기. 맨 앞에 자주 넣으면 deque, 키로 찾으면 dict, 정렬을 유지하며 찾으면 bisect. 7절의 표가 그 판단입니다.
- 지금은 빠른데 나중에 느려질 곳 찾기. 오늘 n = 100 에서 O(n²) 은 1만 걸음이지만, 자료가 100 배(n = 10,000)가 되면 1억 걸음입니다. O(n log n) 이면 약 664 걸음에서 약 13만 걸음(132,877)이 됩니다.
- 2ⁿ 을 피하기. 모든 조합을 훑는 코드는 n = 50 이면 1,125,899,906,842,624 걸음입니다(실험 ①). 한 걸음에 10억 분의 1초라도 약 13 일이 걸립니다. 같은 계산을 저장해 다시 쓰는 동적 계획법, 안 되는 길을 일찍 접는 백트래킹이 이것을 줄입니다.
자주 묻는 것
빅오가 작은 쪽이 늘 더 빠른가요?
아닙니다. 빅오는 n 이 클 때 연산 횟수가 늘어나는 모양만 말합니다. 버린 상수와 작은 항은 n 이 작을 때 크게 남습니다. 칸이 몇 개뿐이면 O(n²) 인 단순한 방법이 O(n log n) 인 방법보다 빠를 수 있습니다. 실제 시간이 궁금하면 n 을 두 배씩 늘려 가며 재 봅니다.
dict 찾기는 왜 O(1) 인데 최악의 경우는 O(n) 인가요?
Python 문서의 dict 시간은 해시 값이 잘 겹치지 않는다고 가정한 보통의 값입니다. 그러면 칸이 아무리 많아도 몇 걸음 만에 찾습니다. 모든 키의 해시가 같은 최악의 경우는 겹친 것들을 하나씩 비교해야 해서 O(n) 이 됩니다.
append 는 가끔 전부 옮긴다는데 왜 O(1) 인가요?
리스트의 자리가 다 차면 더 큰 자리로 전부 옮깁니다. 그 한 번은 O(n) 이지만 자주 일어나지 않아서, 여러 번 넣은 전체 비용을 넣은 횟수로 나누면 한 번에 O(1) 입니다. 이것을 분할 상환(amortized)이라고 부릅니다. 한 번 한 번이 꼭 짧아야 하는 곳에서는 이 점을 기억합니다.
낱말
| 여기서 쓴 말 | 책에서 부르는 말 |
|---|---|
| 걸음이 n 에 따라 늘어나는 모양 | 시간 복잡도(time complexity), 증가 차수(order of growth) |
| 빅오, 이보다 빨리 늘지는 않는다는 한계 | 빅오 표기(Big O notation), 점근 표기(asymptotic notation) |
| 더 드는 메모리의 모양 | 공간 복잡도(space complexity) |
| 그대로 · 한 걸음 더 · 두 배 · 두 배보다 조금 더 · 네 배 · 하나 늘면 두 배 | 상수(constant) · 로그(logarithmic) · 선형(linear) · 선형 로그(linearithmic) · 제곱(quadratic) · 지수(exponential) |
| 가장 나쁠 때 · 보통 · 가장 좋을 때 | 최악(worst case) · 평균(average case) · 최선(best case) |
| 나눠 내기 | 분할 상환 분석(amortized analysis) |
| 작은 항만 버린 근사 | 물결표 근사(tilde approximation, ~) |
| 앞에서부터 하나씩 찾기 · 반씩 잘라 찾기 | 선형 탐색(linear search) · 이진 탐색(binary search) |
출처
- Robert Sedgewick, Kevin Wayne, Algorithms, 1.4 Analysis of Algorithms. 물결표 근사와 증가 차수, 가장 나쁠 때의 약속, 분할 상환 분석, 메모리 세기, 두 배씩 늘려 재기.
- Python 문서: Time complexity of operations on built-in types. 리스트와 dict 의 연산별 시간, dict 의 보통·가장 나쁠 때, append 의 분할 상환, 정렬이 이미 정렬된 입력에서 O(n) 비교.