Re: [問題] 97中山資結

[check (且可)]

用代入展開法
T(n)=4T(n/2)+n^2
    =4(4T((n/2)/2)+(n/2)^2) + n^2
    =16T(n/4)+ 2*n^2
    =16(4T((n/4)/2)+(n/4)^2) + 2*n^2
    =64T(n/8)+ 3*n^2
    = ....
    =4^i*T(n/2^i) + i*n^2
因為T(n/n)=T(1)=1    2^i=n   i=logn
    =n^2*1 + n^2*(logn)
       => O(n^2*(logn))

用n=2^k帶入亦可解出

※ 引述《depend (depend)》之銘言：
: 中山資結的第一題
: T(n)= 1                    if n=1
:       4T(n/2)+theta(n^2)   if n>1
: 設T(n)=O(n^2)
: =>T(n)=4O(n^2/2^2)+n^2=O(n^2)
: 這個步驟是哪裡出錯呢???
: 那正確的複雜度應該要怎麼算阿
: 我用數學的方法計算可是怎麼算都不是n^2*(logn)耶...??
: 麻煩高手解答 謝謝>"<

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 218.170.109.62
→ depend:我看懂了>"< 謝謝原po~