Re: [理工] [資結]-時間複雜度
※ 引述《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)
推
12/05 11:04, , 1F
12/05 11:04, 1F
→
12/05 11:05, , 2F
12/05 11:05, 2F
推
12/05 17:44, , 3F
12/05 17:44, 3F
討論串 (同標題文章)