作者check (且可)
看板Grad-ProbAsk
标题Re: [问题] 97中山资结
时间Tue Mar 24 18:02:51 2009
用代入展开法
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
1F：→ depend:我看懂了>"< 谢谢原po~ 03/24 18:43