알고리즘 분석 입문
알고리즘의 시간·공간 복잡도를 분석하는 방법과 최선·평균·최악 경우의 의미를 설명합니다.
지난 글에서 알고리즘의 정의와 좋은 알고리즘의 5가지 조건을 살펴봤습니다. 이제 두 알고리즘 중 어떤 것이 더 나은지 판단하는 기준인 알고리즘 분석으로 넘어갑니다.
왜 알고리즘을 분석하는가
같은 문제를 해결하는 알고리즘이라도 실행 시간과 메모리 사용량이 크게 다를 수 있습니다. 직접 실행해서 비교할 수도 있지만, 이 방법은 컴퓨터 성능·언어·입력 데이터에 따라 결과가 달라지기 때문에 신뢰하기 어렵습니다. 그래서 수학적으로 알고리즘의 효율성을 측정하는 방법이 필요합니다.
시간 복잡도와 공간 복잡도
알고리즘 분석의 두 가지 핵심 지표입니다.
- 시간 복잡도(Time Complexity): 입력 크기 n에 따라 알고리즘이 수행하는 기본 연산(비교, 대입, 산술 등)의 횟수
- 공간 복잡도(Space Complexity): 알고리즘이 실행되는 동안 사용하는 메모리 용량
둘 다 입력 크기 n의 함수로 표현됩니다. 현대에는 메모리가 저렴해져 시간 복잡도를 더 중시하는 경향이 있습니다.
분석의 3가지 경우
같은 알고리즘이라도 입력 데이터에 따라 수행 횟수가 달라집니다. 그래서 세 가지 경우를 나눠 분석합니다.
최선 경우 (Best Case) — Ω(n)
가장 유리한 입력이 주어졌을 때의 성능입니다. 선형 탐색에서 첫 번째 원소가 바로 목표인 경우처럼 단 1번의 비교로 끝나는 상황입니다. 하한(Lower bound)을 나타냅니다.
평균 경우 (Average Case) — Θ(n)
가능한 모든 입력에 대한 기대 성능입니다. 확률 분포를 가정해야 해서 분석이 복잡하지만, 실제 사용 환경에 가장 근접합니다. 선형 탐색의 평균은 n/2번 비교입니다.
최악 경우 (Worst Case) — O(n)
가장 불리한 입력이 주어졌을 때의 성능입니다. 선형 탐색에서 목표가 마지막 원소이거나 없는 경우 n번 비교가 필요합니다. 실무에서 가장 중요합니다. 최악의 경우가 보장되어야 시스템이 안정적으로 동작하기 때문입니다.
기본 연산 카운팅
알고리즘 분석의 첫 단계는 지배적인 연산을 세는 것입니다.
def sum_array(arr):
total = 0 # 대입 1번
for i in range(len(arr)):
total += arr[i] # 덧셈 + 대입 = 2번, n회 반복
return total # 반환 1번
# 총 연산: 1 + 2n + 1 = 2n + 2여기서 상수 2와 상수 2는 n이 충분히 클 때 의미가 작아집니다. 중요한 것은 n에 비례해 증가한다는 사실, 즉 선형(linear) 성장이라는 점입니다.
점근적 분석의 필요성
입력 크기가 작을 때는 어떤 알고리즘도 충분히 빠릅니다. 중요한 것은 n이 커질 때의 행동입니다.
| n | O(log n) | O(n) | O(n log n) | O(n²) |
|---|---|---|---|---|
| 10 | 3 | 10 | 33 | 100 |
| 1,000 | 10 | 1,000 | 10,000 | 1,000,000 |
| 1,000,000 | 20 | 1,000,000 | 20,000,000 | 10¹² |
n=1,000,000에서 O(n²)는 현대 컴퓨터(초당 10⁹ 연산 기준)로 약 16분이 걸리지만 O(log n)은 즉시 처리됩니다.
# 두 중첩 루프: O(n²)
def naive_pairs(n):
count = 0
for i in range(n): # n번
for j in range(n): # n번
count += 1
return count # 총 n² 번
# 수학 공식 활용: O(1)
def smart_pairs(n):
return n * n # 상수 시간분석 시 주의사항
- 숨겨진 복잡도: 내장 함수(예:
list.sort())도 복잡도가 있습니다. O(n log n) - 입력 크기 정의: 배열의 경우 원소 수, 문자열의 경우 글자 수, 그래프는 정점 수 + 간선 수
- 상수 인자 무시: 실제 성능에서는 상수가 중요할 수 있지만, 점근 분석에서는 무시
정리
- 알고리즘 분석 = 입력 크기 n에 대한 연산 횟수 함수 도출
- 시간 복잡도(연산 횟수) vs 공간 복잡도(메모리)
- 최선/평균/최악 경우 — 실무에서는 최악 경우 위주 분석
- 점근적 분석: n이 충분히 클 때의 성장률만 본다
지난 글: 알고리즘이란 무엇인가
다음 글: 시간·공간 복잡도
읽어주셔서 감사합니다. 😊