マスターメソッドを使用してT（n）= 9T（n/3）+ 2n^2 + n/3の時間複雑さを解く方法は？

Question

f（n）は何ですか？それはn^2か2n^2 + n/3か？そのような質問を解決するには？次のようにマスター定理を想起し、事前

Answer 1

で ありがとう：recusion方程式

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

与えられ、それはE = log(b)/log(c)成り立つ：

1. f(n)は、いくつかのeps > 0ためO(N^(E - eps))であれば、その後、T(n)が入っていますTheta(n^E);
2. f(n)がTheta(N^E)である場合、T(n)はTheta(N^E * log(n))です。
3. f(n)は、いくつかのd < 1とn十分な大きさのためにいくつかのeps > 0、さらにb*f(n/c) <= d*f(n)ためOmega(N^(E + eps))であれば、その後、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))になります。