反復関係を解くには？

Question

この質問は試験に来て、私はそれを行う方法がわからない誰も私を助けたり、いくつかのヒントを与えることができます。私はマスターの方法はここに適用されないと思いますか？ 助けてください。

nを仮定すると、T（N）= T（N/2）+θ（LOGN）

Answer 1

は2の電力である、n = 2^kを言う、そして簡単にするために、lgが対数であるのがT(n) = T(n/2) + lg(n)を言わせベース2およびT(1) = lg(1) = 0。 nについて

T(n) = lg(n) + lg(n/2) + lg(n/4) + ... + lg(1) 
    = lg(2^k) + lg(2^{k-1}) + ... + lg(2^0) 
    = k.lg(2) + (k-1)lg(2) + ... + 0.lg(2) 
    = (k + (k-1) + ... + 0) lg(2) 
    = k(k+1)/2 
    = lg(n)(lg(n)+1)/2 
    = Theta(lg(n)^2). 

は2の電力が、一方がTが増加関数であることに注意し、そしてk = floor(lg(n))そうT(2^k) <= T(n) <= T(2^{k+1})ことができません。上記正確な結果から、我々は（n個のログ）あなたはシータに注目することによって拘束ラフ上位を持つことができます

k(k+1)/2 <= T(n) <= (k+1)(k+2)/2 

ので

T(n) = Theta(floor(lg(n))^2) = Theta(lg(n)^2)