25. Recurrence Relations

1. 점화식이란?

 재귀 알고리즘의 실행 시간을 분석하려면 새로운 도구가 필요하다. 단순 반복문은 시그마(Σ)로 셀 수 있지만, 알고리즘이 자기 자신을 호출하면 얘기가 달라진다.

 

점화식(Recurrence Relation) 은 수열의 항을 이전 항들로 표현하는 식이다.

예를 들어 Selection Sort를 재귀로 구현하면:

• n개짜리 리스트에서 최솟값 찾기: n번
• 나머지 n-1개를 재귀적으로 정렬

이걸 점화식으로 쓰면:

T(n) = n + T(n-1), T(0) = 0

 

풀면: T(n) = n + (n-1) + (n-2) + ... + 1 = Θ(n²)

재귀로 구현해도 문제 크기를 1씩 줄이는 건 너무 느리다. 그래서 "절반씩 나누는" Divide and Conquer(분할정복)이 필요하다.

---

2. Master Theorem

분할정복 알고리즘은 대부분 이 패턴을 따른다:

T(n) = a·T(n/b) + Θ(nᵈ), T(1) = Θ(1)

 

각 파라미터의 의미:

• a: 서브문제 개수 (몇 개로 나누는가)
• b: 입력 크기가 줄어드는 배수 (얼마나 작아지는가)
• d: 재귀 호출 외 작업의 복잡도 (나누고 합치는 데 드는 비용)

Critical exponent e = log_b(a) 를 구한 뒤 d와 비교한다.

조건	결과	직관
d > e	T(n) = Θ(nᵈ)	루트(현재 단계)가 지배
d = e	T(n) = Θ(nᵈ log n)	모든 레벨이 균등하게 기여
d < e	T(n) = Θ(nᵉ) = Θ(n^(log_b a))	리프(가장 깊은 단계)가 지배

 

예시 1 — Merge Sort:

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

 

a=2, b=2, d=1 → e = log₂2 = 1
d = e이므로 T(n) = Θ(n log n)

 

예시 2 — 일반 분할정복:

T(n) = 4T(n/2) + Θ(n)

 

a=4, b=2, d=1 → e = log₂4 = 2
d < e이므로 T(n) = Θ(n²)

 

예시 3:

T(n) = 3T(n/3) + Θ(n²)

 

a=3, b=3, d=2 → e = log₃3 = 1
d > e이므로 T(n) = Θ(n²)

---

3. Linear Recurrence — Generating Function

 Master Theorem은 n/b 형태(입력을 나누는 것)에만 쓸 수 있다. 피보나치처럼 n-1, n-2 형태(빼는 것)엔 적용 불가다. 이때는 Generating Function을 쓴다.

아이디어

점화식은 aₙ이 aₙ₋₁, aₙ₋₂에 의존하고 있어서 직접 풀기 어렵다. 그래서 수열 전체를 하나의 함수로 포장해 버린다:

F(x) = a₀ + a₁x + a₂x² + a₃x³ + ...

 

이렇게 하면 점화식이 F(x)에 대한 대수 방정식으로 바뀌고, 그걸 풀어서 x^n의 계수를 읽으면 aₙ이 나온다.

핵심 트릭: x를 곱하면 계수가 한 칸 밀린다

• F(x)의 x^n 계수 → aₙ
• x·F(x)의 x^n 계수 → aₙ₋₁
• x²·F(x)의 x^n 계수 → aₙ₋₂

풀이 흐름

① F(x) 방정식 세우기

 점화식을 보고 F(x)에서 뭘 빼야 할지 결정한다.

aₙ = aₙ₋₁ + 6aₙ₋₂이면 → F(x) - x·F(x) - 6x²·F(x)를 전개한다.

전개하면:

• n≥2인 항: 점화식에 의해 자동으로 0이 됨
• n=0, n=1 항만 남음

(1 - x - 6x²)F(x) = a₀ + (a₁ - a₀)x

 

주의: x의 계수는 a₁이 아니라 (a₁ - a₀) 다. x를 곱하면 F(x)의 a₀이 x¹ 자리로 밀려오기 때문에, 그걸 빼고 남은 값이 계수가 된다. 추측하지 말고 직접 전개해서 계산하는 습관을 들이자. 연습문제를 혼자 처음 풀 때 주어진 F(x)값을 보정하기 위해서 a_0과 a_1을 그냥 더해서 구했다가 점화식을 직접 전개했을 때의 값과 달라서 뭐가 틀렸는지 찾느라 한참 걸렸다.

 

a₀=1, a₁=1이면: (1 - x - 6x²)F(x) = 1 + (1-1)x = 1

F(x) = 1 / (1 - x - 6x²)

 

② 분모 인수분해 + 부분분수 분해

1 - x - 6x² = (1-3x)(1+2x)이므로:

F(x) = A/(1-3x) + B/(1+2x)

 

A, B 구하는 법: 양변에 분모를 곱한 뒤, 한쪽 항이 0이 되는 x값을 대입한다.

• x = 1/3 대입 → B항 사라짐 → A = 3/5
• x = -1/2 대입 → A항 사라짐 → B = 2/5

③ 등비급수로 계수 추출

등비급수 공식: 1/(1-r) = Σ rⁿ

• 1/(1-3x) = Σ (3x)ⁿ = Σ 3ⁿ xⁿ
• 1/(1+2x) = 1/(1-(-2x)) = Σ (-2x)ⁿ = Σ (-2)ⁿ xⁿ

따라서:

aₙ = (3/5)·3ⁿ + (2/5)·(-2)ⁿ = (3^(n+1) + 2·(-2)ⁿ) / 5

 

검증:

• a₀ = (3 + 2) / 5 = 1 ✓
• a₁ = (9 - 4) / 5 = 1 ✓
• a₂ = (27 + 8) / 5 = 7 ✓ (점화식: 1 + 6·1 = 7)

---

4. 피보나치와 Binet's Formula

피보나치도 같은 방식으로 풀 수 있다.

f₀=0, f₁=1, fₙ = fₙ₋₁ + fₙ₋₂

 

F(x) = x / (1 - x - x²)

분모의 근이 황금비 φ = (1+√5)/2 ≈ 1.618, ψ = (1-√5)/2 ≈ -0.618과 관련되어 있어서, 부분분수 분해 후 정리하면:

fₙ = (φⁿ - ψⁿ) / √5

 

|ψ| < 1이므로 ψⁿ → 0. 피보나치는 지수적으로 증가하고, 충분히 큰 n에서 fₙ ≈ φⁿ / √5가 된다.

---

 

5. 핵심 정리

Master Theorem 요약:

조건	T(n)
d > e = log_b(a)	Θ(nᵈ)
d = e	Θ(nᵈ log n)
d < e	Θ(nᵉ)

 

Generating Function 흐름:

점화식 세우기 → F(x) 방정식 전개 (직접 계산!) → closed form → 부분분수 → 등비급수로 aₙ 추출