Re: [問題] 97中山資結
用代入展開法
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
→
03/24 18:43, , 1F
03/24 18:43, 1F
討論串 (同標題文章)