마스터 방법을 사용하여 T (n) = 9T (n/3) + 2n^2 + n/3의 시간 복잡도를 해결하는 방법?

Question

f (n)은 무엇인지 알 수 없습니까? 그것은 n^2 또는 2n^2 + n/3입니까? 그런 질문을 해결하는 방법? 다음과 같이 마스터 정리 리콜 미리

Answer 1

에 감사 : 일부 eps > 0위한 O(N^(E - eps))에

1. f(n) 있다면, T(n)가되어 다음 recusion 방정식

   T(n) = b*T(n/c) + f(n), 
   

   가 E = log(b)/log(c) 동안 보유에게 주어진 Theta(n^E);

2. f(n)이 Theta(N^E) 인 경우, T(n)은 Theta(N^E * log(n)); f(n) 충분히 큰 일부 eps > 0 및 추가 b*f(n/c) <= d*f(n) 일부 d < 1 및 n에 대한 Omega(N^(E + eps))에있는 경우
3. , 다음 T(n)는 Theta(f(n))입니다.

그렇지 않으면 마스터 정리가 도움이되지 않습니다. 알고리즘에 대한 모든 기본 교과서 또는 Google을 사용하여이 정의를 얻을 수 있습니다.

정의에서 우리는 b = 9과 c = 3 및 f(n) = 2*n^2 + n/3을가집니다. 따라서 사례 2가 E = 2이고 f(n)이 Theta(n^2) 인 것으로 쉽게 나타납니다. 따라서 T(n)은 Theta(n^2 * log(n))입니다.