[理工] [資結]-時間複雜度

[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)嗎?

--
※ 發信站: 批踢踢實業坊(ptt.cc) 
◆ From: 122.116.218.120
推 polomoss:nlgn 沒錯~~你n代5去跑跑看就知道了~
→ NOtWorThy:for loop 跑n次 => x=n  while 跑一次 break
→ NOtWorThy:這樣不是O(n)??
推 abien:這題目本來就有一點問題XD