作者gorocky (哇沙咪)
看板Grad-ProbAsk
標題Re: [理工] [DS]-兩題time complexity
時間Tue Jul 21 16:38:55 2009
※ 引述《nowar100 (拋磚引玉)》之銘言：
: 1)
: 問一個很基本的問題，可是我一直都不會算 Orz||
: for i=1 to n do
: for j=1 to i do
: for k=1 to j do
: x=x+1;
: end
: end
: end
: 問 x=x+1 執行次數為？ 答案是 n(n+1)(n+2) / 6
: 可是我遇到這種邊界會變的，就不會了
: 2)
: T(n) = 2 T( n/2 ) + nlgn
: 答案是 θ(n lg^2 n)，是怎麼算出來的 @@
: 謝謝 ^^
這一題要用級數去做
n i j
__ __ __
\ \ \
/ / / 1 =
__ __ __
i=1 j=1 k=1
n i
__ __
\ \
/ / j =......以此類推 就可以去求出你要的答案了!!
__ __
i=1 j=1
訣竅 觀察你的FOR迴圈的起 始 位置!! 看不懂的話在寫站內信給我!!
級數的符號真難用!!
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 220.136.132.201
1F：推 nowar100:謝謝 07/21 16:58
2F：→ final01:這題是不是有速解? 07/21 20:17
3F：→ nowar100:樓上大大提供一下 A__A 07/21 20:19
4F：推 swon:C(n+3-1,3) 07/22 00:30
5F：→ nowar100:是離散的 1<=i<=j<=k<=n 嘛，有點印象 07/22 09:15