PS에서 Master Theorem

Master Theorem은 알고리즘의 동작 시간을 대략의 수행시간을 big O notation으로 계산하는 방법이다.

 

일반적으로 divide-and-conquer와 같은 recursion에서 자주 사용하며, 입력이 n개인 task를 문제를 입력이 n/b개인 a개의subtask로 나눴을 때, 그 subtask를 f(n)만에 해결할 수 있다면 아래 식과 같이 표현한다.

 

$T(n) = aT(\frac{n}{b}) + f(n)$ (단, a >= 1, b > 1, p >= 0)

 

 Master Theorem은 T(n)에 관한 점화식을 푼다. 그러나 대부분의 PS에서 f(n)은 $\Theta(n^{k}log^{p}n)$으로 정의되니, 이 식에서 답을 도출해 볼 것이다.

 

1. if $log_{b}a < k (\Leftrightarrow a < b^{k})$ then $T(n) = \Theta(n^{k}log^{p}n)$

• task를 subtask로 나누는 것의 load가 subtask의 load보다 큰 경우이다.

2. if $log_{b}a = k (\Leftrightarrow a = b^{k})$ then $T(n) = \Theta(n^{log_{b}a}log_{p+1}n)$

• subtask의 load와 task를 subtask로 나누는 것의 load와 비슷한 경우이다.

3. if $log_{b}a > k (\Leftrightarrow a > b^{k})$ then $T(n) = \Theta(n^{log_{b}a})$

• subtask의 load가 task를 subtask로 나누는 것의 load보다 큰 경우이다.

 

예를 들어, merge sort는 T(n) = 2T(n/2) + O(n)이다. $log_{2}2$ == 1이므로 2)의 case에 해당되고, $\Theta(nlogn)$이 된다.