推 NOtWorThy:他不是會先把for loop跑完一輪 才去跑while loop? 12/05 11:04
→ NOtWorThy:怎感覺大家的理解都是WHILE 嵌在FOR LOOP中? 12/05 11:05
推 polomoss:重點你想的那樣，那這題就沒有意義了~~題目原意應該是此 12/05 17:44
※ 引述《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)嗎?
i=1:
裡面while x初始值n 每次-1 直到扣到<=0
total: n次
i=2:
裡面while x初始值n 每次-2 直到扣到<=0
total: [n/2]次
.
.
.
i=k:
裡面while x初始值n 每次-k 直到扣到<=0
total: [n/k]次
.
.
.
i=n:
裡面while x初始值n 每次-n 直到扣到<=0
total: [n/n]次
-----------------------------------------------------------------
所以total 跑了：
n + [n/2] + [n/3] + ............[n/n] 次
<= n*(1 + 1/2 + 1/3 ＋ ............ + 1/n) 次 (後面為調和級數<logn,
<= n*log(n) 證明請參考各課本 不難找）
所以time complexity = O(nlogn)
小弟卓見 有錯誤請包含糾正
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.115.222.154
※ 編輯: joe1234wu 來自: 140.115.222.154 (12/04 23:31)