PostAddsense


4.5 The master method for solving recurrences Introduction to algorithms


Theorem 4.1 (Master theorem)


상수 a,b는 a ≥ 1 , b > 1 이고, f(n)은 함수, T(n)은 음이 아닌 정수로 구성된 재귀식이 있다고 하자.

$T(n) = aT(n/b) + f(n).$

여기서 n/b는 $\left \lceil n/b \right \rceil$ 또는 $\left \lfloor n/b \right \rfloor$ 를 의미한다. 다음 설명에서 T(n)은 좁은 경계(tight bound)를 갖는다.

  1. 상수 ε > 0 에 대하여 $f(n) = O(n^{\log_{b}a-\epsilon})$ 이면 $T(n) = \Theta(n^{\log_{b}a})$.

  2. $f(n) = \Theta(n^{\log_{b}a})$ 이면, $T(n) = \Theta(n^{\log_{b}a}\lg n)$.

  3. 상수 ε > 0 에 대해 $f(n) = \Omega(n^{\log_{b}a+\epsilon})$ 이고, 상수 c < 1 이며 충분히 큰 n에 대해 $af(n/b) \leq cf(n)$ 이면 $T(n) = \Theta(f(n))$.



Example


  • $T(n) = 3T(n/4) + n\lg n$

a=3, b=4, f(n) = n lg n 이므로 nlog43 = O(n0.793).

$f(n) = \Omega(n^{\log_{4}3+\epsilon})$ 이고, ε ≈ 0.2 이므로 master method - case3를 적용할 수 있다.

충분히 큰 n에 대하여

$af(n/b) = 3(n/4)\lg(n/4) \leq (3/4)n\lg n = cf(n) $

이것은 regularity condition을 만족하므로 $T(n) = \Theta(n\lg n)$.



  • $T(n) = 2T(n/2) + n\lg n$

이 식의 문제점은 다항적으로 크지 않다는 것이다. $f(n)/n^{\log_{b}a} = (n\lg n)/n = \lg n$의 비율은 양의 상수 ε을 가진 nε보다 점근적으로 작다. 따라서 이 재귀식은 case2와 case3 사이의 틈으로 빠지게 된다. 



Exercises


4.5-1
Use the master method to give tight asymptotic bounds for the following recurrences.
a. T(n) = 2T(n/4) + 1.
b. T(n) = 2T(n/4) + √n.
c. T(n) = 2T(n/4) + n.
d. T(n) = 2T(n/4) + n².


a. $T(n) = \Theta(\sqrt n)$
b. $T(n) = \Theta(\sqrt n \lg n)$
c. $T(n) = \Theta(n)$
d. $T(n) = \Theta(n^{2})$



4.5-2
Professor Caesar wishes to develop a matrix-multiplication algorithm that is asymptotically faster than Strassen's algorithm. His algorithm will use the divide-and-conquer method, dividing each matrix into pieces of size n/4 x n/4, and the divide and combine steps together will take Θ(n²) time. He needs to determine how many subproblems his algorithm has to create in order to beat Strassen’s algorithm. If his algorithm creates a subproblems, then the recurrence for the running time T (n) becomes T(n) = aT(n/4) + Θ(n²). What is the largest integer value of a for which Professor Caesar’s algorithm would be asymptotically faster than Strassen’s algorithm?


스트라센 알고리즘보다 빠르기 위해서는 case1을 만족해야한다. 

$\Theta(n^{2}) = O(n^{\log_{4}a-\epsilon})$ 을 만족하려면 a > 16 이어야 하고, 따라서 $T(n) = \Theta(n^{\log_{4}a})$ 이다.

스트라센 알고리즘 실행시간은 Θ(nlg7) 이다. 비교하면 log4a < log27 이고, 이것을 만족하는 a는 48이다.



4.5-3
Use the master method to show that the solution to the binary-search recurrence T(n) = T(n/2) + Θ(1) is T(n) = Θ(lg n). (See Exercise 2.3-5 for a description of binary search.)


a = 1, b = 2, f(n) = Θ(1).
Θ(1) = Θ(nlog21) 이므로 T(n) = Θ(lg n).



4.5-4
Can the master method be applied to the recurrence T(n) = 4T(n/2) + n2lg n? Why or why not? Give an asymptotic upper bound for this recurrence.


a = 4, b = 2, f(n) = n²lg n ≠ O(n2-ε), Ω(n2+ε).
따라서 마스터 정리를 이용할 수 없다.

상계(upper bound) 추측을 이용해 증명할 수 있다.



4.5-5 ★
Consider the regularity condition af(n/b) ≤ cf(n) for some constant c < 1, which is part of case 3 of the master theorem. Give an example of constants a ≥ 1 and b > 1 and a function f(n) that satisfies all the conditions in case 3 of the master theorem except the regularity condition.


a = 1, b = 2, f(n) = n(2-cosn), T(n) = T(n/2) + n(2-cosn).


증명
------------------------------------
$$\frac{n}{2}(2-cos\frac{n}{2}) \leq cn(2-cosn)$$

cosn = 1 일 때, c ≥ 3/2 이다.
cosn = -1 일 때, c ≥ 1/3 이다.
그러므로 regularity condition에 부합하지 않는다.
------------------------------------