作者NOtWorThy ()
看板Grad-ProbAsk
标题[理工] [资结]-时间复杂度
时间Thu Dec 3 23:08:17 2009
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)吗?
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 122.116.218.120
1F：推 polomoss:nlgn 没错~~你n代5去跑跑看就知道了~ 12/03 23:22
2F：→ NOtWorThy:for loop 跑n次 => x=n while 跑一次 break 12/04 18:44
3F：→ NOtWorThy:这样不是O(n)?? 12/04 18:45
4F：推 abien:这题目本来就有一点问题XD 12/05 01:31