time-complexity - マスターメソッドを使用して T(n) = 9T(n/3) + 2n^2 + n/3 の時間の複雑さを解決する方法は?

Question

f(n) が何であるかわかりませんか? n^2 ですか 2n^2 + n/3 ですか? そのような質問をどのように解決しますか？前もって感謝します

Answer 1

主定理を次のように思い出す:

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

それは次のように成り立ちますE = log(b)/log(c):

1. ある場合f(n)は、O(N^(E - eps))あるeps > 0場合T(n)はありTheta(n^E)ます。
2. である場合f(n)は、Theta(N^E)でT(n)あるTheta(N^E * log(n))。
3. f(n)ある場合、さらにOmega(N^(E + eps))ある場合、および十分な大きさがある場合は、ある。eps > 0b*f(n/c) <= d*f(n)d < 1nT(n)Theta(f(n))

そうでなければ、マスター定理は役に立ちません。(この定義は、アルゴリズムに関するすべての基本的な教科書から、または Google を使用して取得できます。)

あなたの定義から、 と と がb = 9ありc = 3ますf(n) = 2*n^2 + n/3。E = 2したがって、ケース 2 がとで成り立つことは簡単に示さf(n)れTheta(n^2)ます。したがって、T(n)ですTheta(n^2 * log(n))。