[알고리즘 기초] 03 점화식(Recurrence)

1. 점화식(Recurrence)

• 더 작은 입력에 대해 자신의 값으로 함수를 나타내는 방정식 또는 부등식
• 분할정복 알고리즘의 수행시간을 자연스럽게 표현 가능

ex)

$T(n)=T(n-1)+\Theta(1)$

해석 : 각 재귀 호출에 걸리는 시간 ($T(n)$)은 "상수시간($\Theta(1)$) + 새로운 재귀 호출이 필요한 시간($T(n-1)$)"

$T(n) = a\cdot T(n/b)+f(n)$

해석 : 각 부분문제($a\cdot T(n/b)$)는 크기가 원래 문제의 $1/b$이고 분할과 결합 과정은 합쳐서 $f(n)$시간 걸림

---

2. 점화식을 푸는 방법

1) 치환법(substituition method)

• 한계를 추측한 후 그 추측식이 옮음을 증명하기 위해 귀납법 사용
• 문제가 쉬운 경우에만 적용(단점)

2) 재귀트리 방법(recursion-tree method)

• 점화식을 각 노드가 재귀 호출의 해당 레벨에 따른 비용을 나타내도록 만든 트리로 변환하여 점화식을 품
• 그리고 이를 위해 합의 합계를 구하는 기법 이용

3) 마스터 방법(master method)

 

*** 참고

• 여기서는 치환법과 재귀트리를 이용한 방법을 다룸(마스터 방법 다루지 않음)
  
• 쉬운 문제인 경우 치환법을 이용해 풀 수 있으나 복잡한 문제인 경우 ①재귀트리를 이용하여 추측식을 구하고, ②구한 추측식을 치환법을 사용하여 증명하는 방법으로 문제를 해결