동작 원리: 연산 세기에서 마스터 정리까지

복잡도를 구하는 과정은 생각보다 기계적입니다. 기본 연산을 정하고, 코드의 구조(순차, 반복, 중첩, 재귀)를 따라 횟수를 n의 식으로 쓴 다음, 가장 큰 항만 남기면 됩니다. 이 장에서는 작은 예제로 그 과정을 한 단계씩 따라갑니다.

1단계: 기본 연산 정하기

기본 연산은 입력 크기와 상관없이 일정한 시간이 드는 동작입니다. 비교, 덧셈, 배열 인덱싱, 변수 대입 등이 여기에 들어갑니다. 정렬이라면 "비교 횟수", 탐색이라면 "원소를 확인한 횟수"처럼 알고리즘의 핵심 동작 하나를 골라 세면 충분합니다.

주의할 점은 한 줄짜리 코드가 기본 연산이 아닐 수 있다는 것입니다. Python의 x in some_list는 리스트를 처음부터 훑으므로 O(n)이고, sorted(items)는 O(n log n), 문자열 s + t는 길이만큼 복사합니다.

2단계: 구조에 따라 횟수 세기

아래 함수의 비교 횟수를 직접 세어 봅니다.

def count_pairs_with_sum(items, target):
    count = 0
    n = len(items)
    for i in range(n):              # i = 0 .. n-1
        for j in range(i + 1, n):   # n-1-i 번
            if items[i] + items[j] == target:
                count += 1
    return count

안쪽 반복은 i가 0일 때 n-1번, 1일 때 n-2번, 마지막에는 0번 돕니다. 합은 (n-1) + (n-2) + ... + 0 = n(n-1)/2입니다. 이를 펼치면 n²/2 - n/2이고, 상수와 낮은 차수 항을 버리면 Θ(n²)입니다. 작은 n에서 실제로 세어 보면 공식과 맞습니다.

n이 두 배가 될 때 횟수가 약 네 배가 되는 것이 n²의 특징입니다.

3단계: 절반씩 줄이면 log n

이진 탐색은 정렬된 리스트에서 범위를 매번 절반으로 줄입니다. 범위 크기가 16 → 8 → 4 → 2 → 1로 줄어드는 데 4번이면 충분하고, 원소가 1,024개여도 약 10번이면 됩니다. "n을 몇 번 반으로 나눠야 1이 되는가"가 바로 log₂ n입니다.

def halving_steps(n):
    steps = 0
    while n > 1:
        n //= 2
        steps += 1
    return steps

for n in (16, 1_024, 1_000_000):
    print(n, halving_steps(n))
# 16 4
# 1024 10
# 1000000 19

로그의 밑(2, 3, 10)은 상수배 차이(log₂ n = log₁₀ n / log₁₀ 2)일 뿐이라 점근 표기에서는 밑을 쓰지 않고 O(log n)이라고 적습니다. 바깥 반복이 n번이고 안쪽이 절반씩 줄어드는 반복이라면 O(n log n)이 됩니다.

4단계: 재귀는 점화식으로

재귀 함수는 "자기 자신을 몇 번, 얼마나 작은 입력으로 부르는가"와 "그 밖에 하는 일"로 점화식을 세웁니다.

def merge_sort(items):
    if len(items) <= 1:                 # 바닥: T(1) = O(1)
        return items
    mid = len(items) // 2
    left = merge_sort(items[:mid])      # T(n/2)
    right = merge_sort(items[mid:])     # T(n/2)
    merged, i, j = [], 0, 0             # 병합: O(n)
    while i < len(left) and j < len(right):
        if left[i] <= right[j]:
            merged.append(left[i]); i += 1
        else:
            merged.append(right[j]); j += 1
    return merged + left[i:] + right[j:]

점화식은 T(n) = 2T(n/2) + O(n)입니다. 재귀 트리로 보면 각 층에서 병합하는 원소의 합이 n이고, 층의 수가 log n이므로 전체는 O(n log n)입니다.

마스터 정리를 쉬운 말로

T(n) = a·T(n/b) + f(n) 꼴, 즉 "크기 n/b인 하위 문제 a개를 풀고, 나누고 합치는 데 f(n)이 드는" 재귀에는 마스터 정리를 쓸 수 있습니다. 핵심은 잎(가장 작은 하위 문제)들이 하는 일의 양 n^(log_b a)와 맨 위에서 하는 일 f(n)을 비교하는 것입니다.

• 잎 쪽이 더 크면(f가 다항식 차이로 작으면): 잎이 이깁니다. T(n) = Θ(n^(log_b a))
• 둘이 같은 차수면: 모든 층이 비슷한 일을 하므로 층 수만큼 곱합니다. T(n) = Θ(n^(log_b a) · log n)
• 위쪽이 더 크면(f가 다항식 차이로 크고, 규칙성 조건을 만족하면): 맨 위가 이깁니다. T(n) = Θ(f(n))

T(n) = T(n-1) + T(n-2) + O(1)인 단순 재귀 피보나치처럼 크기가 비율이 아니라 뺄셈으로 줄어드는 재귀에는 마스터 정리를 쓸 수 없습니다. 이 경우 호출 수가 약 1.618^n으로 늘어나는 지수 시간입니다.

정리

• 기본 연산을 정하고, 순차는 더하고 중첩은 곱하고 절반씩 줄면 로그를 씁니다.
• 한 줄짜리 내장 연산(in list, 정렬, 문자열 결합)의 비용도 세어야 합니다.
• 재귀는 점화식으로 쓰고, aT(n/b) + f(n) 꼴이면 잎과 맨 위의 일을 비교하는 마스터 정리로 풉니다.