점화식 (Recurrence)

• 정의

  • 일반적인 형태는 함수 자신을 사용하여 정수 또는 실수에 대해 함수를 표현하는 방정식 또는 부등식. 둘 이상의 케이스는
    • 재귀 케이스 - 더 작은 입력에 대한 함수의 재귀호출이 포함
    • 베이스 케이스 - 재귀 호출이 포함되지 않음

• 예시

  • 한 수열 {$a_n$}가 있을 때 점화식은
    • a_n = f(a_{n-1}, a_{n-2}, ... , a_{n-k})
    • f는 함수(연산)이며, a_n을 구할 때, 이전 항들 (a_{n-1},a_{n-2},....)의 값을 사용
  • 1차 선형 점화식 : a_n = c • a_{n-1} 한 단계 전 항만 이용
  • 2차 선형 점화식 : a_n = p • a_{n-1} + q • a_{n-2} 두 단계 전 항까지 이용
  • 피보나치 수열 : F_n = F_{n-1} + F_{n-2}, (n ≥ 2)$ (초기값 F_0 = 0, F_1 = 1이 필요)
  • 팩토리얼 : n! = n × (n-1)!, (n ≥ 1)$ (초기값 $0! = 1$을 이용)
  • 등비수열 : a_n = r • a_{n-1} (초기값 a_1에 공비 r을 이용)

• 초기값(초항)과 해(Closed-Form)

  • 초기값(초항) : 점화식 스스로만으로는 수열을 완전히 결정할 수 없어, 위 예시처럼 초기값을 제공 해야함
  • 점화식의 해(Closed-Form) : 특정 점화식은 수열을 간단한 식(지수함수, 다항식, 조항식 등)으로 표현할 수 있음

• 활용

  • 알고리즘 설계 : 동적 계획법 (DP: dynamic plan)에서 부분 문제의 해를 점화식으로 정의, 문제를 효율적으로 해결
  • 수학적 분석 : 수열의 거동을 파악하거나, 복잡도(이진 트리 높이 등)을 계산할 때 점화식을 세우고 풀어볼 수 있음
  • 재귀 함수 : 재귀 함수를 작성할 때, 구조가 점화식과 동일하게 표현될 수 있음

• 주요 해결방법

  • 치환법 (substitution method) : 한계를 추측한 후 추측식이 옮음을 증명하기 위해 수학적 귀납법을 이용. 가장 강력한 방법이지만 좋은 추측과 귀납적 증명을 만들어야 함 (Introduction of Algorithm 4.3)
  • 재귀 트리 방법 (recursion-tree method) : 각 노드가 재귀 호출 해당 레벨에 따른 비용을 나타내도록 만든 트리로 변환하여 점화식을 푼다 (Introduction of Algorithm 4.4) 합의 한계를 구하는 기법 또는 경계 합산 기법을 사용
  • 마스터 방법 (master method) : T(n) = _aT(n/b) + f(n) 형식으로 된 점화식의 답을 제시
  • 아크라-바지 방법 (Akra-Bazzi method) : 미적분을 포함한 분할 정복 재귀를 푸는 일반적인 방법 (4.7), 더 복잡한 재귀에 사용