algorithm - アルゴリズムのランニング コストを求める

Question

次の再発を解決できません

T(n) = 3T(n/5) + lg^2 n

私の仕事: マスター定理の適用

 a=3 b=5

 n^log5^3n= n^log^0.65

これはこれにつながり、n^0=1これはlと比較できませんog^2n

再帰ツリーも試しましたが、複雑になりすぎました。助けてください。

Answer 1

T(n) = a*T(n/b) + f(n)
ここで、

a = 3
b = 5
f(n) = (lg(n))^2

さて、マスターの定理の最初のケースによれば、

ある定数 e > 0 に対して f(n) = O(n^logb(a−e)) の場合、T(n) = Θ(n^logb(a)) です。

e = 3-sqrt(5)とすると、 n^ logb
(a−e) = n^log5(3-(3-sqrt(5))) = n^log5(sqrt(5)) = n^ 0.5 = sqrt(n)。

したがって、 (lg(n))^2とsqrt(n)を比較する必要があります。これら 2 つの関数のグラフ
をプロットすると、 (lg(n))^2 = O(sqrt(n))であることが明確にわかります。

b = 5、a = 3、e = 3-sqrt(5) の場合、f(n) = O(n^logb(a−e)) なので、
T(n) = Θ(n^logb(a))

=> T(n) = Θ(n^0.68)