점화식 (Recurrence Relations)

지난 글에서 분할 상환 분석을 통해 개별 연산의 비싼 비용이 전체 평균에 어떤 영향을 미치는지 살펴봤습니다. 이번에는 재귀 알고리즘의 수행 시간을 수학적으로 표현하는 도구인 점화식(Recurrence Relation)을 다룹니다. 병합 정렬이나 퀵 정렬 같은 분할 정복 알고리즘을 분석할 때 점화식을 세우고 풀 수 있어야 빅오 복잡도를 제대로 이해할 수 있습니다.

점화식이란

점화식은 함수 T(n)을 더 작은 입력 크기의 T 값으로 표현한 수식입니다. 예를 들어 크기 n인 배열을 병합 정렬로 정렬할 때, 배열을 반으로 나눠 각각 재귀 정렬한 뒤 병합하므로:

T(n) = 2 · T(n/2) + n      (기저: T(1) = 1)

여기서 2T(n/2)는 두 번의 재귀 호출, n은 병합 비용입니다.

대표 점화식 유형

아래 네 가지 형태가 실무에서 가장 자주 등장합니다.

T(n) = 2T(n/2) + n — 준선형

병합 정렬의 점화식으로, 답은 Θ(n log n) 입니다. 각 재귀 호출에서 n만큼 일을 하는 구조입니다.

T(n) = T(n/2) + 1 — 로그

이진 탐색은 매 단계 검색 범위를 반으로 줄이고 상수 비용만 발생합니다. 답은 Θ(log n) 입니다.

def binary_search(arr, target):
    lo, hi = 0, len(arr) - 1
    while lo <= hi:               # T(n) = T(n/2) + 1
        mid = (lo + hi) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            lo = mid + 1
        else:
            hi = mid - 1
    return -1

T(n) = T(n-1) + n — 이차

선택 정렬은 매 패스마다 남은 원소를 모두 스캔하므로 T(n) = T(n−1) + n → Θ(n²) 입니다.

T(n) = 2T(n-1) + 1 — 지수

하노이 탑은 n개 원판을 옮기기 위해 2번의 (n−1) 재귀 호출이 필요합니다. 답은 Θ(2ⁿ) 으로 지수 폭발이 일어납니다.

재귀 트리로 시각화하기

재귀 트리(Recursion Tree)는 점화식의 재귀 호출을 트리로 펼쳐 각 레벨의 총 비용을 합산하는 방법입니다.

T(n) = 2T(n/2) + n의 재귀 트리를 전개하면:

레벨	노드 수	각 노드 비용	레벨 총 비용
0	1	n	n
1	2	n/2	n
2	4	n/4	n
⋮	⋮	⋮	n
log n	n	1	n

레벨이 log₂n 개이고 각 레벨마다 n의 비용이 발생하므로 총합은 n log n 입니다.

점화식 표기 관례

점화식을 세울 때는 기저 조건(base case)을 반드시 명시해야 합니다.

T(1) = 1          ← 입력 크기 1일 때의 비용
T(n) = aT(n/b) + f(n)
       ─────────   ───
       재귀 호출   결합 비용

• a : 한 번의 재귀 호출에서 만들어지는 하위 문제 수
• b : 각 하위 문제의 크기 축소 비율 (n/b)
• f(n) : 분할과 결합에 드는 비용

풀이 방법 세 가지

점화식을 풀어 닫힌 형식(closed form)으로 만드는 방법은 크게 세 가지입니다.

1. 반복 대입법(Substitution Method) — 추측 후 수학적 귀납법으로 증명
2. 재귀 트리법(Recursion Tree) — 위처럼 시각적으로 전개 후 합산
3. 마스터 정리(Master Theorem) — a, b, f(n)을 비교해 빠르게 답 도출

반복 대입법의 예를 들면:

T(n) = T(n/2) + 1

T(n) = T(n/4) + 1 + 1
     = T(n/8) + 1 + 1 + 1
     = T(n/2^k) + k
     
n/2^k = 1 → k = log₂n 일 때 기저 도달
∴ T(n) = T(1) + log₂n = 1 + log₂n = Θ(log n)

정리

• 점화식은 재귀 알고리즘의 시간 복잡도를 수식으로 표현합니다.
• 대표 형태인 분할 정복 점화식 T(n) = aT(n/b) + f(n)을 이해하는 것이 핵심입니다.
• 재귀 트리는 직관적으로 각 레벨의 비용을 합산할 수 있는 강력한 도구입니다.
• 다음 글에서 다룰 마스터 정리는 이 점화식 형태를 단 세 가지 경우로 빠르게 해결합니다.

---

지난 글: 분할 상환 분석

다음 글: 마스터 정리

읽어주셔서 감사합니다. 😊