作者s987692 (阿誠)
看板Grad-ProbAsk
標題[問題] 資結 複雜度~~
時間Tue Apr 7 23:39:27 2009
for i from 1 to n do
{ x = n
while x>0 do
{x= x-i
}
}
問 order是多少
答案是 O(nlogn)~
答案在計算 while 次數時 是 n-ki = 1
我想問的是 它這樣遞減下來值也不一定是1呀
想問一下為什麼這樣寫~
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 114.42.212.174
1F：推 ginwer:應該是剪到不能減為止 就是當X<0就停了 04/08 13:10
2F：→ ginwer:所以可能假設就剪到1這樣 也比較好算 04/08 13:11
3F：推 morning12345:你想寫n-ki=0也可以 這樣更好算:Σk=n*調和數列=nlgn 04/08 14:21
4F：→ s987692:我就是想的跟樓上一樣~3Q~ 04/08 15:43