Algorithms
마스터 정리
yonsweng
2020. 5. 10. 09:20
마스터 정리를 사용하기 위해선 시간 복잡도 점화식이 다음과 같이 정의되어야 한다.
$$T(n) = aT(n/b) + f(n)$$
그리고 다음과 같이 세 가지 제약 조건이 있다.
1. $f(n)$은 다항식(polynomial function)이어야 한다. 단, $f(n)$이 다항식이 아니더라도 극명하게 적용될 수 있음을 증명하면 사용할 수 있다. ($n^2$ > $n log n$ 또는 $n^2$ < $n^2 log n$)
2. a와 b가 $a \geq 1$과 $b > 1$인 양의 실수여야 한다. 재귀를 호출할 때 그 호출 비용이 현재보다 작아야 한다는 것을 의미한다.
3. 정규 조건(regularity condition) ${af(n/b)} \leq {cf(n)}$을 만족하는 $c < 1$가 존재해야 한다. 이는 부분 문제가 현재 문제보다 작아져야 함을 의미한다.
위 조건들을 만족하면 양의 정수 $e(epsilon)$에 대해
$$1. T(n) = O(n^{log_b a}) \ if\ f(n) = n^{{log_b a} - e}$$
$$2. T(n) = O(n^{log_b a} log n) \ if\ f(n) = n^{log_b a}$$
$$3. T(n) = O(f(n)) \ if\ f(n) = n^{{log_b a} + e}$$
참고