作者depend (depend)
看板Grad-ProbAsk
标题[问题] 97中山资结
时间Tue Mar 24 16:50:32 2009
中山资结的第一题
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: 140.116.142.19
1F：→ xmisery:master theorem; n^(log2 4)=n^2=θ(n^2) 03/24 17:15
2F：→ xmisery:∴T(n)=θ( (n^2)*logn ) 03/24 17:16
3F：→ depend:可是他的题目有说不能用公式解耶>"< 03/24 17:21
4F：→ spits:令n=2^k 代进去解 并不会很难解 03/24 17:56