推 lightergogo:請問一下 Σ(1/i)怎麼變成logn的? 12/04 02:47
→ spring60569:微積分 12/04 04:06
推 polomoss:調和函數→O(lgn) 用積分可以證明 12/04 10:23
※ 引述《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