Re: [理工] [資結]-時間複雜度
※ 引述《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
推
12/04 02:47, , 1F
12/04 02:47, 1F
→
12/04 04:06, , 2F
12/04 04:06, 2F
推
12/04 10:23, , 3F
12/04 10:23, 3F
討論串 (同標題文章)