복잡도와 빅오: 느린 코드를 알아보는 눈
같은 답을 내는 코드가 데이터 1,000개에서는 똑같이 빠르다가 100만 개에서는 1초와 몇 시간으로 갈리는 이유를 따져요. 실행 시간 대신 연산 횟수의 증가율을 보는 법, 빅오로 줄여 쓰는 규칙, O(1)부터 O(2ⁿ)까지 자주 만나는 복잡도와 두 배 실험, 코드에서 복잡도를 읽는 법과 in이나 pop(0)처럼 한 줄에 숨은 반복을 찾는 법을 직접 세어 확인해요. 이진 탐색의 로그, 최선과 평균과 최악, append의 분할 상환, 공간 복잡도, 그리고 빅오가 알려 주지 않는 것까지 다뤄요.
알고리즘 트랙의 첫 강의예요. 프로그래밍 기초 트랙에서 반복문을 겹치면 횟수가 곱으로 늘어난다고 했고, 수학 기초 트랙의 지수와 로그 강의에서는 빅오 표를 잠깐 봤어요. 이번에는 그 감각을 제대로 다져요. 같은 답을 내는 두 코드가 데이터 1,000개에서는 똑같이 빠르다가, 100만 개에서는 하나는 1초 안에 끝나고 다른 하나는 몇 시간 걸리기도 해요. 이 차이를 코드를 돌려 보기 전에 알아보는 눈이 복잡도예요.
같은 답, 다른 속도
회원 번호 목록에 중복이 있는지 확인하는 방법 세 가지를 짜고, 각각 기본 연산(비교나 확인)을 몇 번 하는지 세어 볼게요.
import random
from functools import cmp_to_key
def dup_pairs(items): # 방법 1: 모든 쌍을 비교해요
steps = 0
for i in range(len(items)):
for j in range(i + 1, len(items)):
steps += 1
if items[i] == items[j]:
return True, steps
return False, steps
def dup_sort(items): # 방법 2: 정렬한 뒤 이웃끼리만 비교해요
steps = 0
def compare(a, b):
nonlocal steps
steps += 1
return (a > b) - (a < b)
ordered = sorted(items, key=cmp_to_key(compare))
for a, b in zip(ordered, ordered[1:]):
steps += 1
if a == b:
return True, steps
return False, steps
def dup_set(items): # 방법 3: 본 것을 집합에 기억해요
steps, seen = 0, set()
for x in items:
steps += 1
if x in seen:
return True, steps
seen.add(x)
return False, steps
random.seed(1)
for n in (1_000, 2_000, 4_000):
data = random.sample(range(10 * n), n) # 중복이 없는 경우: 끝까지 다 봐야 해요
print(f"n={n:>5,} 쌍 비교 {dup_pairs(data)[1]:>9,}번 정렬 {dup_sort(data)[1]:>6,}번 집합 {dup_set(data)[1]:>5,}번")
n=1,000 쌍 비교 499,500번 정렬 9,668번 집합 1,000번
n=2,000 쌍 비교 1,999,000번 정렬 21,286번 집합 2,000번
n=4,000 쌍 비교 7,998,000번 정렬 46,635번 집합 4,000번
셋 다 정답을 내요. 그런데 n이 두 배가 될 때마다 쌍 비교는 4배, 정렬은 2.2배쯤, 집합은 딱 2배로 늘어요(정렬의 비교 횟수는 파이썬 버전에 따라 조금 다를 수 있어요). 실제 시간도 재 볼게요.
import time
def seconds(func, *args, repeat=1):
start = time.perf_counter()
for _ in range(repeat):
func(*args)
return (time.perf_counter() - start) / repeat
small, big = random.sample(range(10**7), 400), random.sample(range(10**7), 4_000)
t_small, t_big = seconds(dup_pairs, small, repeat=5), seconds(dup_pairs, big)
print("쌍 비교: n이 10배가 되자 시간이 50배 넘게 늘었나요?", t_big / t_small > 50)
per_second = (4_000 * 3_999 / 2) / t_big
million = random.sample(range(10**8), 1_000_000)
estimate = (1_000_000 * 999_999 / 2) / per_second
print("100만 개를 쌍 비교로 검사하면:", "1시간 넘게 걸려요" if estimate > 3600 else "1시간 안에 끝나요")
print("100만 개를 집합으로 검사하면:", "1초 안에 끝나요" if seconds(dup_set, million) < 1 else "1초 넘게 걸려요")
쌍 비교: n이 10배가 되자 시간이 50배 넘게 늘었나요? True
100만 개를 쌍 비교로 검사하면: 1시간 넘게 걸려요
100만 개를 집합으로 검사하면: 1초 안에 끝나요
1,000개일 때는 셋 다 눈 깜짝할 사이에 끝나서 차이를 느낄 수 없어요. 그래서 작은 데이터로 시험할 때는 문제가 보이지 않다가, 서비스가 커진 어느 날 갑자기 느려져요. 쌍 비교로 100만 개를 검사하면 어림잡아 몇 시간이 걸리는데, 집합으로는 1초도 안 걸려요.
시간 대신 횟수를 세요
실행 시간은 컴퓨터의 성능, 언어, 그 순간 함께 돌던 프로그램에 따라 달라져요. 같은 코드를 두 번 재도 결과가 조금씩 달라요. 그래서 알고리즘을 비교할 때는 입력의 크기 n이 커질 때 기본 연산의 횟수가 어떻게 자라는가를 봐요. 이게 시간 복잡도예요. 메모리를 얼마나 더 쓰는지는 공간 복잡도라고 해요.
기본 연산은 비교, 더하기, 값 하나 읽기처럼 한 번에 끝나는 일이에요. 한 번에 걸리는 시간은 컴퓨터마다 다르지만, 몇 번 하는지는 코드만 보고도 셀 수 있어요.
빅오: 가장 빨리 자라는 항만 남겨요
연산 횟수를 정확히 세면 3n² + 5n + 100 같은 식이 나와요. n이 커질 때 각 항이 얼마나 차지하는지 볼게요.
for n in (10, 100, 1_000, 10_000):
total = 3 * n**2 + 5 * n + 100
print(f"n={n:>6,} 3n²+5n+100 = {total:>11,} 그중 3n²의 몫 {3 * n**2 / total:.2%}")
n= 10 3n²+5n+100 = 450 그중 3n²의 몫 66.67%
n= 100 3n²+5n+100 = 30,600 그중 3n²의 몫 98.04%
n= 1,000 3n²+5n+100 = 3,005,100 그중 3n²의 몫 99.83%
n=10,000 3n²+5n+100 = 300,050,100 그중 3n²의 몫 99.98%
n이 100만 돼도 3n²이 98%예요. 커질수록 나머지 항은 의미가 없어져요. 그래서 가장 빨리 자라는 항만 남기고, 앞에 곱해진 상수도 버려서 O(n²)이라고 써요. "빅오 n제곱"이라고 읽어요.
상수까지 버리는 이유는, 상수는 컴퓨터와 언어가 바꿀 수 있지만 증가율은 바꾸지 못하기 때문이에요. 연산을 100n번 하는 방법과 n²번 하는 방법을 비교해 볼게요.
print(f"{'n':>7} {'100n':>11} {'n²':>13} 더 적은 쪽")
for n in (10, 50, 100, 1_000, 10_000):
a, b = 100 * n, n * n
print(f"{n:>7,} {a:>11,} {b:>13,} {'n²' if b < a else '100n' if a < b else '같아요'}")
n 100n n² 더 적은 쪽
10 1,000 100 n²
50 5,000 2,500 n²
100 10,000 10,000 같아요
1,000 100,000 1,000,000 100n
10,000 1,000,000 100,000,000 100n
n이 100보다 작을 때는 n²번 하는 쪽이 오히려 적어요. 하지만 100을 넘으면 100n이 앞서고, 그 차이는 계속 벌어져요. 빅오는 n이 충분히 클 때 누가 이기는지를 알려 줘요. 그래서 상수 100은 빼고 O(n)과 O(n²)으로만 비교해요. 로그의 밑도 같은 이유로 신경 쓰지 않아요. log₂ n과 log₁₀ n은 상수배 차이일 뿐이라(지수와 로그 강의) 그냥 O(log n)이라고 써요.
수학으로 쓰면 이래요. 어떤 양수 와 가 있어서 이상인 모든 에 대해 아래가 성립하면 이라고 해요.
"충분히 큰 n에서는 g(n)의 상수배를 넘지 않는다", 즉 이보다 빨리 자라지는 않는다는 위쪽 한계예요. 아래쪽 한계는 Ω(오메가), 위아래가 딱 맞는 증가율은 Θ(세타)로 따로 쓰지만, 실무에서는 보통 빅오를 "딱 이만큼 자란다"는 뜻으로 써요.
자주 만나는 복잡도
대표적인 복잡도가 n에 따라 어떻게 자라는지 표로 볼게요. 마지막 칸은 n을 두 배로 늘리면 횟수가 몇 배가 되는지예요.
import math
growth = {
"O(1)": lambda n: 1,
"O(log n)": lambda n: math.log2(n),
"O(n)": lambda n: n,
"O(n log n)": lambda n: n * math.log2(n),
"O(n²)": lambda n: n**2,
"O(2ⁿ)": lambda n: 2**n,
}
def show(v):
return f"{v:,.0f}" if v < 10**9 else f"{v:.1e}"
print(f"{'':>11}" + "".join(f"{'n=' + str(n):>12}" for n in (10, 20, 40, 80)) + " n을 2배로")
for name, f in growth.items():
ratio = "제곱이 돼요" if name == "O(2ⁿ)" else f"{f(2000) / f(1000):.1f}배"
print(f"{name:>11}" + "".join(f"{show(f(n)):>12}" for n in (10, 20, 40, 80)) + f" {ratio}")
years = 2**80 / 1e9 / (365.25 * 24 * 3600)
print(f"1초에 10억 번 계산해도 n=80인 O(2ⁿ)은 약 {years / 1e4:,.0f}만 년")
n=10 n=20 n=40 n=80 n을 2배로
O(1) 1 1 1 1 1.0배
O(log n) 3 4 5 6 1.1배
O(n) 10 20 40 80 2.0배
O(n log n) 33 86 213 506 2.2배
O(n²) 100 400 1,600 6,400 4.0배
O(2ⁿ) 1,024 1,048,576 1.1e+12 1.2e+24 제곱이 돼요
1초에 10억 번 계산해도 n=80인 O(2ⁿ)은 약 3,831만 년
- O(1): n과 상관없이 일정해요. 리스트의 i번째 값 읽기, 딕셔너리 조회가 그래요.
- O(log n): n이 두 배가 돼도 한 번 늘어요. 이진 탐색, 데이터베이스 인덱스.
- O(n): 한 번 훑기. 합계, 최댓값, 리스트에서 값 찾기.
- O(n log n): 좋은 정렬 알고리즘. n보다 조금 더 빨리 자라요.
- O(n²): 모든 쌍 비교. n이 10배가 되면 100배가 돼요.
- O(2ⁿ): 모든 부분집합 확인. n이 하나 늘 때마다 두 배라, 조합론 강의에서 본 경우의 수 폭발이 여기서 나와요.
마지막 칸은 실제로도 쓸모가 있어요. 코드의 복잡도를 모를 때 n을 두 배씩 늘려 가며 시간을 재고 비율을 보면 돼요. 거의 그대로면 O(1)이나 O(log n), 2배면 O(n), 2배를 조금 넘으면 O(n log n), 4배면 O(n²), 8배면 O(n³)이에요. 이 강의에서는 이걸 두 배 실험이라고 부를게요.
대략의 기준도 알아 두면 좋아요. 파이썬으로 짠 단순한 반복은 1초에 천만 번 단위로 돌아요(컴퓨터마다 달라요). 그러니 n이 100만일 때 O(n log n)인 2,000만 번은 몇 초 안에 끝나지만, O(n²)인 1조 번은 몇 시간에서 하루 가까이 걸려요.
코드에서 복잡도 읽기
돌려 보지 않고 코드만 보고 복잡도를 읽는 규칙은 세 가지예요.
- 차례로 이어지면 더해요. O(n) 반복 뒤에 O(n) 반복이 또 오면 O(2n), 즉 O(n)이에요. O(n) 뒤에 O(n²)이 오면 큰 쪽만 남아 O(n²)이에요.
- 안에 들어가면 곱해요. n번 도는 반복 안에서 m번 도는 반복은 O(n·m)이에요.
- 반씩 줄이면 로그예요. 남은 범위를 매번 반으로 줄이거나, 거꾸로 매번 두 배로 키우면 O(log n)이에요.
네 가지 반복의 횟수를 세어 확인해 볼게요.
def fixed_inner(n): # 바깥 n번, 안쪽은 늘 10번
count = 0
for i in range(n):
for j in range(10):
count += 1
return count
def halving(n): # 남은 범위를 반씩 줄여요
count = 0
while n > 1:
n //= 2
count += 1
return count
def triangle(n): # 안쪽이 i번: 0 + 1 + ... + (n - 1)
count = 0
for i in range(n):
for j in range(i):
count += 1
return count
def outer_doubling(n): # 바깥 n번, 안쪽은 1, 2, 4, 8, ...로 키워요
count = 0
for i in range(n):
j = 1
while j < n:
j *= 2
count += 1
return count
patterns = {
"안쪽이 늘 10번": fixed_inner,
"반씩 줄이기": halving,
"안쪽이 i번": triangle,
"바깥 n번, 안쪽 2배씩": outer_doubling,
}
for label, f in patterns.items():
one, two = f(1_024), f(2_048)
print(f"{label}: n=1,024일 때 {one:,}번, n=2,048일 때 {two:,}번 ({two / one:.2f}배)")
안쪽이 늘 10번: n=1,024일 때 10,240번, n=2,048일 때 20,480번 (2.00배)
반씩 줄이기: n=1,024일 때 10번, n=2,048일 때 11번 (1.10배)
안쪽이 i번: n=1,024일 때 523,776번, n=2,048일 때 2,096,128번 (4.00배)
바깥 n번, 안쪽 2배씩: n=1,024일 때 10,240번, n=2,048일 때 22,528번 (2.20배)
- 안쪽이 늘 10번이면 n × 10이라 O(n)이에요. 상수 10은 버려요.
- 반씩 줄이면 n이 두 배가 돼도 한 번만 늘어서 O(log n)이에요.
- 안쪽이 i번이면 0 + 1 + ... + (n - 1) = n(n - 1)/2번이에요(증명 강의에서 귀납법으로 보인 공식이에요). 가장 빨리 자라는 n²/2가 남아 O(n²)이에요. 안쪽이 평균 절반만 돈다고 덜 나쁜 게 아니에요.
- 바깥 n번 안에서 두 배씩 키우면 n × log n이라 O(n log n)이에요.
n이 1,024일 때 첫째와 넷째는 횟수가 똑같아요(log₂ 1,024 = 10이니까요). 한 점만 봐서는 구별할 수 없고, n이 커질 때 어떻게 자라는지를 봐야 알 수 있어요.
한 줄에 숨은 반복
반복은 for문에만 있는 게 아니에요. 한 줄짜리 코드가 속에서 반복을 돌기도 해요. 두 회원 목록에서 공통 회원을 찾아볼게요.
members_a = [f"user{i}" for i in range(0, 20_000, 2)] # 짝수 번호 1만 명
members_b = [f"user{i}" for i in range(0, 20_000, 3)] # 3의 배수 번호 6,667명
def common_slow(a, b):
return [x for x in a if x in b] # in이 리스트 b를 처음부터 훑어요
def common_fast(a, b):
b_set = set(b) # 한 번만 집합으로 바꿔 두면
return [x for x in a if x in b_set] # in이 거의 한 번에 끝나요
print("공통 회원:", f"{len(common_fast(members_a, members_b)):,}명")
print("결과가 같나요?", common_slow(members_a, members_b) == common_fast(members_a, members_b))
slow = seconds(common_slow, members_a, members_b)
fast = seconds(common_fast, members_a, members_b, repeat=20)
print("집합으로 바꾸니 100배 넘게 빨라졌나요?", slow / fast > 100)
공통 회원: 3,334명
결과가 같나요? True
집합으로 바꾸니 100배 넘게 빨라졌나요? True
x in b는 한 줄이라 가벼워 보이지만, b가 리스트면 처음부터 하나씩 비교해요. a의 길이를 n, b의 길이를 m이라 하면 common_slow는 O(n·m)이에요. 입력이 둘이면 문자도 둘을 써요. b를 한 번 집합으로 바꿔 두면 바꾸는 데 O(m), 확인 한 번에 평균 O(1)이라 전체가 O(n + m)이 돼요.
파이썬에서 자주 쓰는 연산의 복잡도를 정리하면 이래요.
| 코드 | 복잡도 | 이유 |
|---|---|---|
len(리스트), 리스트[i] | O(1) | 길이를 따로 기억하고, i번째 자리를 바로 계산해요 |
리스트.append(x), 리스트.pop() | O(1) | 맨 뒤만 건드려요(append는 아래 분할 상환 참고) |
x in 리스트, 리스트.index(x) | O(n) | 처음부터 하나씩 비교해요 |
리스트.remove(x), 리스트.pop(0), 리스트.insert(0, x) | O(n) | 빈칸을 메우거나 자리를 만들려고 뒤의 원소를 모두 옮겨요 |
리스트[a:b] | 잘라낸 길이만큼 | 그만큼 새로 복사해요 |
x in 집합, 딕셔너리[키] | 평균 O(1) | 해시로 자리를 바로 계산해요 |
sorted(리스트), 리스트.sort() | O(n log n) | 비교로 정렬하는 방법 중 가장 빠른 수준이에요(정렬 강의) |
min(리스트), sum(리스트) | O(n) | 모두 한 번씩 봐요 |
데이터베이스 트랙에서 본 N+1 문제도 숨은 반복이에요. 반복문 안에서 질문을 하나씩 보내면, 질문 하나는 빨라도 n번을 보내요. 네트워크를 한 번 오가는 시간이 메모리에서 값 하나를 비교하는 시간보다 수천 배 넘게 길어서, n이 작아도 금방 티가 나요.
반씩 줄이면 로그
정렬된 데이터에서는 가운데를 보고 절반을 버리는 이진 탐색을 쓸 수 있어요. 몇 번 만에 끝나는지 세어 볼게요.
def binary_search(ordered, target):
lo, hi, steps = 0, len(ordered) - 1, 0
while lo <= hi:
steps += 1
mid = (lo + hi) // 2
if ordered[mid] == target:
return mid, steps
if ordered[mid] < target:
lo = mid + 1
else:
hi = mid - 1
return -1, steps
for n in (1_000, 1_000_000, 1_000_000_000):
evens = range(0, 2 * n, 2) # 0, 2, 4, ... 정렬된 n개(range는 메모리를 거의 안 써요)
_, last = binary_search(evens, 2 * (n - 1)) # 맨 끝 값
_, missing = binary_search(evens, 1) # 없는 값
print(f"n={n:>13,} 맨 끝 값 {last:>2}번 없는 값 {missing:>2}번 (log₂ n ≈ {math.log2(n):.1f})")
n= 1,000 맨 끝 값 10번 없는 값 10번 (log₂ n ≈ 10.0)
n= 1,000,000 맨 끝 값 20번 없는 값 20번 (log₂ n ≈ 19.9)
n=1,000,000,000 맨 끝 값 30번 없는 값 30번 (log₂ n ≈ 29.9)
10억 개에서 30번이에요. 하나씩 보면 최악 10억 번인데요. n이 1,000배가 될 때마다 딱 10번씩 늘어요(2¹⁰ = 1,024이니까요). 조건은 하나, 데이터가 정렬돼 있어야 해요. 데이터베이스 인덱스가 빠른 이유도 같아요. B-트리가 정렬된 값을 층층이 나눠 담아 두니, 몇 단계만 내려가면 원하는 값에 닿아요. 파이썬에는 이진 탐색을 해 주는 bisect 모듈도 있어요.
최선, 평균, 최악
리스트에서 값 하나를 찾을 때 첫 칸에 있으면 1번(최선), 없으면 n번(최악), 평균으로는 n/2번쯤 비교해요. 셋이 다를 수 있으니 복잡도를 말할 때는 어느 경우인지가 중요해요.
- 따로 말이 없으면 보통 최악의 경우를 말해요. 서비스는 언젠가 최악의 입력을 만나고, 공격자는 일부러 최악의 입력을 만들어 보내기도 해요.
- 평균을 말하는 관례가 있는 것도 있어요. 해시 테이블의 조회는 평균 O(1)이지만 최악은 O(n)이에요(해시 테이블 강의). 퀵 정렬은 평균 O(n log n), 최악 O(n²)이에요(정렬 강의).
- 맨 처음 예제의
dup_pairs도 중복이 앞쪽에 있으면 금방 끝나요. 그래서 일부러 중복이 없는 최악의 데이터로 쟀어요.
분할 상환: 가끔 비싼 한 번
리스트의 append는 O(1)이라고 했는데, 사실 가끔은 비싸요. 리스트는 원소를 이어진 메모리에 담는데, 빈자리가 다 차면 더 큰 자리를 새로 잡고 원소를 모두 옮겨야 하거든요. 얼마나 자주 그런지 세어 볼게요.
import sys
lst, grows, moved = [], 0, 0
size = sys.getsizeof(lst)
for i in range(1_000_000):
lst.append(i)
if sys.getsizeof(lst) != size: # 빈자리가 모자라 더 큰 자리를 잡은 순간
grows += 1
moved += len(lst) - 1 # 그때까지의 원소를 새 자리로 옮겨야 할 수 있어요
size = sys.getsizeof(lst)
print("append 100만 번 중 자리를 늘린 횟수:", grows)
print("옮긴 원소 수를 모두 더하면 n의 몇 배:", round(moved / len(lst), 1))
append 100만 번 중 자리를 늘린 횟수: 86
옮긴 원소 수를 모두 더하면 n의 몇 배: 8.4
100만 번 중 자리를 늘린 건 86번뿐이에요(정확한 횟수는 파이썬 버전에 따라 다를 수 있어요). 늘릴 때마다 지금 크기에 비례해서 넉넉하게 늘리기 때문이에요. 옮긴 원소를 모두 더해도 n의 8배 남짓이라, 원소 하나당 평균으로는 상수 번이에요. 이렇게 가끔 비싼 일을 전체에 나눠 보면 상수인 경우를 **분할 상환 O(1)**이라고 해요.
반대로 자리가 모자랄 때마다 딱 한 칸씩만 늘린다면 매번 옮겨야 해서, 옮긴 횟수의 합이 1 + 2 + ... + n이 되고 전체가 O(n²)이 돼요. 크기에 비례해 늘리는 게 핵심이에요. 다만 응답 시간이 아주 중요한 곳에서는 이 "가끔 비싼 한 번"이 문제가 되기도 해요.
공간 복잡도
시간만큼 메모리도 따져야 해요. 100만 개의 제곱을 더하는 두 방법이 메모리를 얼마나 쓰는지 재 볼게요.
import tracemalloc
def peak_mb(func):
tracemalloc.start()
func()
peak = tracemalloc.get_traced_memory()[1]
tracemalloc.stop()
return peak / 1024**2
print(f"리스트에 모아서 더하기: {peak_mb(lambda: sum([i * i for i in range(1_000_000)])):.0f}MB")
print(f"하나씩 만들며 더하기: {peak_mb(lambda: sum(i * i for i in range(1_000_000))):.2f}MB")
리스트에 모아서 더하기: 39MB
하나씩 만들며 더하기: 0.00MB
리스트에 다 모았다가 더하면 100만 개를 한꺼번에 들고 있어야 해서 O(n)의 메모리를 써요. 대괄호를 뺀 제너레이터는 하나씩 만들어 더하고 버리니 O(1)이에요. 시간은 둘 다 O(n)인데 메모리가 달라요.
맨 처음의 집합 방식도 공짜가 아니에요. 본 값을 모두 기억하느라 메모리를 O(n) 더 써요. 메모리를 내주고 시간을 사는 거래예요. 서버 트랙에서 본 캐시도 같은 거래고요. 데이터가 메모리에 다 들어가지 않을 만큼 크면 이 거래를 할 수 없으니, 데이터를 나눠서 처리하거나 디스크를 잘 다루는 데이터베이스에 맡겨요. 재귀 호출도 부를 때마다 메모리를 쓰는데, 이건 재귀와 동적 계획법 강의에서 다뤄요.
빅오가 알려 주지 않는 것
- 작은 n에서는 상수가 이겨요. 위의 100n과 n² 비교처럼요. 파이썬의 정렬도 짧은 구간은 단순한 삽입 정렬로 처리해요. n이 작으면 그게 더 빠르거든요.
- 메모리를 읽는 순서도 속도를 바꿔요. 같은 O(n)이라도 메모리를 차례로 읽으면 빠르고, 여기저기 건너뛰며 읽으면 느려요. 컴퓨터 과학 심화 트랙의 컴퓨터 구조 강의에서 다루는 캐시 이야기예요.
- 느린 원인은 알고리즘 밖에 있을 때가 많아요. 실제 서비스가 느린 이유는 데이터베이스 질문, 네트워크, 디스크인 경우가 많아요.
그래서 순서가 중요해요. 먼저 재고, 가장 오래 걸리는 곳을 찾은 다음, 그 부분의 복잡도를 따져서 고치고, 다시 재요. 파이썬에서는 python -m cProfile -s cumtime 내프로그램.py로 함수마다 걸린 시간을 볼 수 있어요. 재 보지 않고 짐작으로 고치면 엉뚱한 곳을 손보기 쉬워요.
실습
sorted()로 10만, 20만, 40만 개의 무작위 수를 정렬하는 시간을seconds로 재고 비율을 보세요. 2배를 조금 넘나요?- 빈 리스트에
insert(0, x)로 1만, 2만, 4만 개를 넣는 시간을 재 보세요. 몇 배씩 늘어나나요? 표를 보고 이유를 설명해 보세요. - 세 목록에 모두 있는 회원을 찾는 함수를 O(n²) 없이 만들어 보세요.
dup_pairs에서 중복이 맨 앞 두 칸에 있으면 몇 번 만에 끝나나요? 최선과 최악의 경우를 n으로 말해 보세요.- 분할 상환 실험에서 자리가 모자랄 때마다 한 칸씩만 늘린다면, 옮긴 원소 수의 합이 얼마일지 n = 100만으로 계산해 보세요.
자주 하는 실수
- 작은 데이터로만 시험한다. 1,000개에서 빠르다고 100만 개에서도 빠른 건 아니에요. 실제 크기나 그 10배로 재 봐요.
- 한 줄에 숨은 반복을 못 본다. 반복문 안의
in 리스트,remove,pop(0), 데이터베이스 질문을 먼저 의심해요. - 빅오를 실행 시간으로 착각한다. O(n)이 O(n²)보다 언제나 빠른 게 아니라, n이 충분히 크면 이길 뿐이에요.
- 재 보지 않고 고친다. 짐작한 곳은 병목이 아닐 때가 많아요.
- 평균과 최악을 섞는다. 평균 O(1)인 구조도 최악은 다를 수 있어요.
- 메모리를 잊는다. 시간을 아끼려다 메모리가 바닥나면 프로그램이 멈춰요.
점검 문제
- 알고리즘을 비교할 때 실행 시간보다 연산 횟수의 증가율을 보는 이유는?
- 연산 횟수가 5n² + 300n + 2,000인 코드의 복잡도를 빅오로 쓰고, 그렇게 줄이는 이유를 말해 보세요.
- n을 두 배로 늘렸더니 시간이 약 4배가 됐어요. 복잡도를 어떻게 짐작할 수 있나요?
- 정렬된 10억 개에서 이진 탐색은 최대 몇 번쯤 비교하나요? 정렬돼 있지 않다면요?
for x in a:안에서if x in b:를 쓰는 코드(a의 길이는 n, b는 길이 m인 리스트)의 복잡도와 고치는 법은?append가 가끔 오래 걸리는데도 O(1)이라고 하는 이유는?- 집합으로 중복을 검사하는 방법이 아끼는 것과 대신 쓰는 것은?
- O(n²)인 방법이 O(n log n)인 방법보다 빠를 수 있는 경우는?
정답
- 실행 시간은 컴퓨터, 언어, 그때의 상황에 따라 달라지지만, 입력이 커질 때 연산 횟수가 자라는 모양은 코드가 정하기 때문이에요. 그래서 데이터가 커졌을 때 어떻게 될지 미리 알 수 있어요.
- O(n²)이에요. n이 커지면 5n²이 거의 전부를 차지하고, 앞의 상수 5는 컴퓨터나 언어에 따라 달라지는 값이라 증가율을 비교하는 데는 의미가 없어요.
- 두 배에 4배면 n²에 비례해 자란다는 뜻이라 O(n²)일 가능성이 커요. n을 몇 번 더 두 배로 늘려서 비율이 계속 4배 근처인지 확인해요.
- log₂ 10억이 약 30이라 30번쯤이에요. 정렬돼 있지 않으면 하나씩 봐야 해서 최악 10억 번이에요.
- a를 돌 때마다 b를 처음부터 훑으니 O(n·m)이에요. 반복 전에 b를 한 번 집합으로 바꾸면 O(n + m)이 돼요.
- 자리를 늘릴 때 크기에 비례해 넉넉하게 늘려서 비싼 옮기기는 드물게 일어나고, 전체에 나누면 원소 하나당 상수 번이기 때문이에요. 이걸 분할 상환 O(1)이라고 해요.
- 시간을 O(n²)에서 O(n)으로 아끼는 대신, 본 값을 모두 기억하느라 메모리를 O(n) 더 써요.
- n이 작을 때예요. 빅오가 버린 상수가 작은 n에서는 결과를 바꿀 수 있어요. 그래서 파이썬의 정렬도 짧은 구간은 삽입 정렬로 처리해요.
다음 강의
오늘 표에서 pop(0)과 insert(0, x)는 O(n)이고, append와 pop()은 O(1)이었어요. 같은 리스트인데 왜 앞과 뒤가 다를까요? 다음 강의에서는 데이터를 메모리에 늘어놓는 기본 방식인 배열과 연결 리스트, 그리고 그 위에 만든 스택과 큐를 다루면서 이 차이를 속부터 이해해요.