作者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