4.분할정복 4.5 점화식을 풀기 위한 마스터 방법 T(n) = aT(n/b) + f(n) 마스터 방법은 위와 같은 점화식을 푸는 기본 지침을 제공한다. 여기서 a≥1, b>1 인 상수이고 f(n)은 점근적으로 양인 함수다. 마스터 정리 정리 4.1 (마스터 정리) a≥1, b>1 인 상수이고 f(n)이 양의 함수라 하고, 음이 아닌 정수에 대해 T(n)이 다음 점화식에 의해 정의된다고 하자. T(n) = aT(n/b) + f(n) 여기서 n/b는 ⌈n/b⌉ 또는 ⌊n/b⌋을 뜻하는 것으로 이해한다. 그러면 T(n)의 점근적 한계는 다음과 같다. ...
4.분할정복 4.4 점화식을 풀기 위한 재귀 트리 방법 **재귀 트리(recursion tree)**에서는 각 노드가 재귀 호출되는 하위 문제 하나의 비용을 나타낸다. 트리의 각 레벨마다 그 비용을 합한 후 모든 레벨당 비용을 합한다. 예시: T(n) = 3T(n/4)+cn^2 T(n) 은 cn^2 + T(n/4) 3개로 이루어진다. 각 T(n/4)는 c(n/4)^2 + T(n/16) 3개로 이루어 진다. 즉 맨 위부터 각 레벨은 cn^2 1개, c(n/4)^2 3개, c(n/16)^2 9개 .. 로 반복됨을 알 수 있다. 이것이 어느정도 깊이까지 반복될까? 크기를 살펴보면 n -> n/4 -> n/16 이므로 레벨 i 에서는 n/(4^i) 임을 유추할 수 있다. 따라서 4^i = n 일때까지 반복되므로 i = log_4(n) 이라는 정수일때 까지 반복된다. i는 0단계부터 였으므로 총 횟수 log_4(n) + 1개 이다. 레벨 i = log_4(n) 이다. ...
4.분할정복 4.3 점화식을 풀기 위한 치환 치환(Substitution)법 : 귀납 가정을 더 작은 문제에 적용할 때 추측한 해로 치환한다. 해의 모양을 추측한다. 상수들의 값을 찾아내기 위해 수학적 귀납법을 사용하고 그 해가 제대로 동작함을 보인다. 이 책에서는 결과로 나올 해의 모양을 추측하여 치환하는 것에 대한 설명이 많다. 하지만 실제로 양 변에서 공통된 모양을 추출하여 새로운 수열로 치환함으로서 풀 수 있는 점화식 이많다. 예시