作者joe1234wu ()
看板Grad-ProbAsk
标题Re: [理工] [资结]-时间复杂度
时间Fri Dec 4 23:29:47 2009
※ 引述《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)
1F：推 NOtWorThy:他不是会先把for loop跑完一轮 才去跑while loop? 12/05 11:04
2F：→ NOtWorThy:怎感觉大家的理解都是WHILE 嵌在FOR LOOP中? 12/05 11:05
3F：推 polomoss:重点你想的那样，那这题就没有意义了~~题目原意应该是此 12/05 17:44