次の式があります。
W(n) = w(n/3) + lg(n)
W(1) = Theta(1)
そして、その時間の複雑さを見つけたいです。マスター定理では解決できないので（誰でも確認できますか）、「手」で解決しました
木のように考えれば、一本しかないでしょうW(1)。
他のすべての についてn != 1は、合計のように書くことができます:
sum_{i=0}^{log3(n)-1}ln\frac{n}{3i}
この質問に対する私の答えは次のとおりです。
w(n) = sum_{i=0}^{log3(n)-1}ln\frac{n}{3i}
私の問題は、この合計を単純化する方法がわからないことです!
誰かが私にそれを行う方法を説明できますか?
代用しn = 3^kます。
W(3^0) = 1
W(3^k) = W(3^(k-1)) + lg(3^k) = W(3^(k-1)) + lg(3)*k,
代用しT(k) = W(3^k)ます。
T(0) = 1
T(k) = T(k-1) + lg(3)*k.
ことを帰納法によって確認する
T(k) = 1 + lg(3) * sum_{j=1}^k j = 1 + lg(3) * (k+1)*k/2.
置換を元に戻します。
W(n) = 1 + lg(3) * (log3(n)+1)*log3(n)/2 = 1 + (lg(n)/lg(3)+1)*lg(n)/2.
これはマスター定理を満たしています。
ケース2がおよび で適用されるようにa=1、 、b=3、およびとします。したがって、.f(n)=lg nc=0k=1w(n)=Theta(lg^2 n)
最終的な合計を分析できます。
w(n) = sum_{i=1}^{log3(n)-1}ln\frac{n}{3i}
= sum_{i=1}^{log3(n)-1}ln(n/3)-ln i
= (log3(n)-1)ln(n/3)-ln((log3(n)-1)!)
= Theta(ln^2(n))-Theta(ln((log3(n)-1)!)
= Theta(ln^2(n))-Theta((log3(n)-1)ln(log3(n)-1))
= Theta(ln^2(n))-Theta(ln n * ln(ln n))
= Theta(ln^2(n))