복잡도 분석 안내서 · 1/6
복잡도 분석은 알고리즘이 입력 크기에 따라 시간과 메모리를 얼마나 더 쓰는지를 따지는 방법입니다. "이 코드는 0.3초 걸린다"는 측정값은 컴퓨터, 언어, 입력 데이터에 따라 달라지지만, "입력이 두 배가 되면 실행 시간이 네 배가 된다"는 성질은 어느 환경에서나 거의 그대로 유지됩니다. 복잡도 분석은 바로 이 성장의 모양을 다룹니다. 이 장에서는 입력 크기, 점근 표기(O, Ω, Θ), 최선·평균·최악의 경우, 그리고 앞으로 계속 쓰게 될 용어를 정리합니다.
분석은 입력 크기를 정하는 데서 시작합니다. 리스트라면 원소 수, 문자열이라면 길이가 보통 n입니다. 그래프처럼 정점 수 V와 간선 수 E 두 변수를 함께 써야 하는 경우도 있고, 두 문자열을 비교하는 문제라면 각 길이 m과 n을 따로 둡니다.
정수 하나를 입력으로 받는 함수는 조심해야 합니다. 입력 크기는 값 자체가 아니라 그 수를 적는 데 필요한 자릿수(비트 수)입니다. 그래서 2부터 √n까지 나눠 보는 소수 판별은 값 n에 대해서는 O(√n)이지만, 비트 수 b에 대해서는 O(2^(b/2))인 지수 시간입니다.
점근 표기는 n이 충분히 커졌을 때 함수가 자라는 속도를 비교하는 말입니다.
f(n) ≤ c·g(n)이면 f(n) = O(g(n))이라고 씁니다. "g보다 빠르게 자라지 않는다"는 뜻입니다.f(n) ≥ c·g(n)이면 f(n) = Ω(g(n))입니다. "적어도 g만큼은 자란다"는 뜻입니다.f(n) = Θ(g(n))입니다. 성장 속도가 g와 같은 차수라는 뜻입니다.예를 들어 f(n) = 3n² + 5n + 20은 n ≥ 1에서 3n² ≤ f(n) ≤ 28n²이므로 Θ(n²)입니다. O(n³)이라고 써도 틀리지는 않지만 느슨한 상한이라 정보가 적습니다. 실무에서 "이 함수는 O(n²)이다"라고 말할 때는 대개 Θ의 뜻으로 씁니다.
상수와 낮은 차수 항을 버리는 이유는 n이 커질수록 가장 높은 차수 항이 전체를 좌우하기 때문입니다. 아래 코드로 비율을 직접 확인할 수 있습니다.
def f(n):
return 3 * n * n + 5 * n + 20
for n in (10, 100, 1_000, 10_000):
print(n, f(n), round(f(n) / (n * n), 4))
# 10 370 3.7
# 100 30520 3.052
# 1000 3005020 3.005
# 10000 300050020 3.0005비율이 상수 3으로 다가갑니다. 즉 f는 결국 n²의 상수배처럼 움직이고, 상수 3은 하드웨어나 구현에 따라 바뀌는 값이므로 표기에서 뺍니다.
흔한 오해는 "O는 최악의 경우, Ω는 최선의 경우"라는 생각입니다. 실제로는 두 가지가 서로 다른 질문입니다.
선형 탐색은 찾는 값이 맨 앞에 있으면 비교 1번으로 끝나고(최선 Θ(1)), 없거나 맨 끝에 있으면 n번 비교합니다(최악 Θ(n)). 값이 리스트 안에 고르게 있다고 가정하면 평균 비교 횟수는 (n + 1) / 2이고, 이것도 Θ(n)입니다.
def linear_search(items, target):
comparisons = 0
for i, x in enumerate(items):
comparisons += 1
if x == target:
return i, comparisons
return -1, comparisons
data = [7, 3, 9, 4, 1]
print(linear_search(data, 7)) # (0, 1) 최선의 경우
print(linear_search(data, 1)) # (4, 5) 끝에 있는 경우
print(linear_search(data, 8)) # (-1, 5) 없는 경우 = 최악보통은 최악의 경우를 기준으로 말합니다. 사용자가 어떤 입력을 넣을지 모르므로 "어떤 입력이 와도 이 이상은 걸리지 않는다"는 보장이 가장 쓸모 있기 때문입니다.
공간 복잡도는 알고리즘이 쓰는 추가 메모리가 입력 크기에 따라 어떻게 자라는지를 봅니다. 입력 자체를 빼고 계산한 것을 보조 공간(auxiliary space)이라고 부릅니다. 같은 문제라도 메모리를 더 써서 시간을 줄이는 선택이 자주 나옵니다.
def has_duplicate_slow(items): # 시간 O(n²), 보조 공간 O(1)
for i in range(len(items)):
for j in range(i + 1, len(items)):
if items[i] == items[j]:
return True
return False
def has_duplicate_fast(items): # 시간 O(n) 평균, 보조 공간 O(n)
seen = set()
for x in items:
if x in seen:
return True
seen.add(x)
return Falsein list, 반복되는 정렬처럼 숨은 비용을 찾을 때| 용어 | 뜻 |
|---|---|
| 시간 복잡도 | 기본 연산 횟수가 n에 따라 자라는 정도 |
| 공간 복잡도 | 추가 메모리가 n에 따라 자라는 정도 |
| 점근 | n이 충분히 커졌을 때의 경향 |
| 상환(amortized) 분석 | 여러 연산의 총비용을 연산 수로 나눈 평균 보장 |
| 다항 시간 | O(n^k) 꼴, k는 상수 |
| 지수 시간 | O(2^n)처럼 n이 지수에 있는 꼴 |
댓글 0개
로그인 · 로그인하면 댓글을 남길 수 있습니다.