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)의 점근적 한계는 다음과 같다.
\[
- \ \ 상수 \ \ e에 \ \ 대해 \ \ f(n) =O(n^{log_b{a-e}})이면, \ \ T(n) = Θ(n^{log_ba})이다. \
- \ \ f(n)=Θ(n^{log_ba})이면, \ \ T(n)=Θ(n^{log_ba}log_2n)이다. \
- \ \ 상수 e(>0)에 \ \ 대해 \ \ f(n)=Ω(n^{log_b{a+e}})이고 \ \ 상수 \ \ c(<1)와 \ \ 충분히 \ \ 큰 \ \ 모든 \ \ n에 \ \ 대해 \ \ af(n/b)≤cf(n)이면,\ \ \ T(n) = Θ(f(n))이다. \]
세 경우 모두
\[함수 \ \ f(n)과 \ \ 함수 \ \ n^{log_ba}\]를 비교하고 있다. 경우 1과 같이 후자가 더 크다면 해는
\[T(n) = Θ(n^{log_ba})\]이다. 경우 3과 같이 함수 f(n)이 더 크다면 해는
\[T(n) = Θ(f(n))\]이다. 경우 2와 같이 두 함수가 같은 크기라면 로그 성분을 곱해 해는
\[T(n) = Θ(n^{log_ba}log_2n) = Θ(f(n)log_2n)\]이 된다.
참고 사항
경우 1
f(n)이 n^{log_ba}보다 작아야 할 뿐 아니라 다항식적으로 작아야 한다. 즉, f(n)은 점근적으로 상수 e > 0에 대해 1/n^e과 견줄만한 비율로 n^{log_ba}보다 작아야 한다.
경우 3
마찬가지로 f(n)이 다항식적으로 커야한다. 이에 더해 af(n/b) ≤ cf(n) 이라는 정규(regularity)조건을 만족시켜야 한다.
마스터 정리는 위 사항들로 인해 모든 가능성을 다루고 있지 않고 틈이 있다.
마스터 방법 사용하기
예시 1
\[T(n) = 9T(n/3) + n \ \ \\ a=9, \ \ b=3, \ \ f(n)=n 이므로 \ \ n^{log_ba}=n^{log_39}=Θ(n^2) \\ e=1일때 \ \ f(n)=O(n^{log_3{9-e}})이므로 \ \ 마스터 \ \ 정리 \ \ 경우 \ \ 1을 \ \ 적용하여 \\ T(n)=Θ(n^2) \\\]예시 2
\[2. \ \ T(n) = T(2n/3)+1 \\ a=1, \ \ b=3/2, \ \ f(n)=1 \ \ 이므로 \ \ n^{log_ba}=n^{log_{3/2}1}=n^0=1 \\ f(n)=Θ(n^{log_ba})=Θ(1)이므로 \ \ 경우 \ \ 2를 \ \ 적용하면 \\ T(n)=Θ(log_2n)\]예시 3
\[3. \ \ T(n)=3T(n/4)+nlog_2n \\ a=3, \ \ b=4, \ \ f(n)=nlog_2n 이므로 \ \ n^{log_ba}=n^{log_43}=O(n^{0.793}) \\ e<1일 \ \ 때, \ \ f(n) =Ω(n^{log_4{3+e}})이다. \\ af(n/b)=3(n/4)log_2{n/4} ≤ (3/4)nlog_2n = cf(n) 이므로 \\ c = 3/4 일때, \ \ 충분히 \ \ 큰 \ \ n에 \ \ 대해 \ \ 정규 \ \ 조건이 \ \ 만족한다.\\ 따라서, \ \ T(n) =Θ(nlog_2n)이다.\]예시 4
\[T(n) = 2T(n/2) + nlog_2n \\ a=2, \ \ b=2, \ \ f(n)=nlog_2n이고 \ \ n^{log_ba}=n이지만 \ \ 마스터 \ \ 방법을 \ \ 적용할 \ \ 수 \ \ 없다. \\ f(n)/n^{log_ba}=(nlog_2n)/n=log_2n의 \ \ 비율은 \ \ 어떤 \ \ 양의 \ \ 상수 \ \ e에 \ \ 대해서도 \ \ 점근적으로 \ \ n^e보다 \ \ 작기 \ \ 때문이다.\]