마스터 정리(Master Theorem)

마스터 정리는 재귀를 활용한 점화식을 푸는 방법을 알려준다. 다른 것과 다르게 재귀를 사용한 알고리즘은 시간 복잡도를 구하는 것이 어려운데 마스터 정리를 사용하면 아주 간단하게 해결할 수 있다.

 

재귀 알고리즘의 점화식은 다음과 같은 형태를 띄고 있다.

 

$$T(n) = aT(n / b) + f(n) (단, a  ≥ 1, a > 1, f(n)은 점근적으로 양)$$

 

f(n)이 점근적으로 양이라는 말은 충분히 큰 n에 대하여 f(n)이 양이라는 뜻이다.

 

점화식에서 a, b, f(n)을 가지고 시간 복잡도를 계산한다. 다음과 같이 세 가지 경우가 있다.

 

1. $f(n) < n^{log_ba}$

2. $f(n) > n^{log_ba}$

3. $f(n) = n^{log_ba}$

 

1의 시간 복잡도 T(n) = θ($n^{log_ba}$)

2의 시간 복잡도 T(n) = θ($f(n)$)

3의 시간 복잡도 T(n) = θ($f(n)×lgn$)

 

예 1

$$T(n) = 9T(n / 3) + n$$

a = 9, b = 3, f(n) = n

$n<n^{log_39}=n^2$이므로 1번 경우에 해당한다. 그러므로 시간 복잡도 T(n) = θ($n^2$)

 

예 2

$$T(n) = T(2n / 3) + 1$$

a = 1, b = 3 / 2, f(n) = 1

$n^{log_{3 \over 2}1}=n^0=1$이므로 3번 경우에 해당한다. 그러므로 시간 복잡도 T(n) = θ(logn)