[理工] [DS]時間複雜度

[jim055006 (好崩潰)]

Let T(n)=Θ(f(n)). Derive f(n) in the simplest formula for

         n    n^2
T(n)=4T(---)+-----  ,T(c)=c, if c<2.
         2   logn


我是用直接帶入法去算

T(n)=4T(n/2)+n^2/logn

    =4[4T(n/4))+(n/2)^2/log(n/2)]+n^2/logn

    =4^2T(n/2^2)+n^2/log(n/2)+n^2/logn

    :                                                令k=lgn
    :
    =4^kT(n/2^k)+n^2/log(n/2^[k-1])+....+n^2/logn

    =4^lgn+n^2(1/log2+...+1/logn)
           ~~~~~~~~~~~~~~~~~~~~~~
            └ 然後我在這裡卡住了....
               這邊是跟調和數那個有關係嗎??
               不知道要怎麼往下算
               有請高手解答XDDD

鋼溫!!!!



--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 223.138.226.199
推 Byzantin:k = lgn , (1/log2+...+1/logn) = (1/k + 1/(k-1) + ...
→ Byzantin: = lgk , n^2(lgk) = (n^2)lglgk
→ jim055006:喔喔.....從後面帶入算回來就對了....我好像懂了..鋼溫
推 simonjoker:用mater method吧?
→ jim055006:就算用extend master theorem也無用 ..因為k不會>=1