作者CMJ0121 (请多指教!!)
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Thu Dec 3 23:53:24 2009
※ 引述《NOtWorThy ()》之铭言：
: Let T(n) be the running time of Foo(n). Find the order of T.
: Foo(int n){
: for i from 1 to n
: x = n
: while x > 0 do
: x = x - i
: }
: 为什麽是O(nlgn)?
: 不是O(n)吗?
首先我先确认 Foo函数是不是...
Foo( int n )
{
for i from 1 to n
{
x = n;
while x > 0 do
x = x - i;
end while
}
}
所以全部运算次数为: Σ 上高斯(n/i)
故复杂度为 O(Σ 上高斯(n/i) ) = O( Σ(n/i) + n )
= O( nΣ(1/i) +n )
= O( nlnn )
如果不是你可以 end了
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 219.71.69.211
1F：推 lightergogo:请问一下 Σ(1/i)怎麽变成logn的? 12/04 02:47
2F：→ spring60569:微积分 12/04 04:06
3F：推 polomoss:调和函数→O(lgn) 用积分可以证明 12/04 10:23