Re: [理工] [DS]-兩題time complexity
※ 引述《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
推
07/21 16:58, , 1F
07/21 16:58, 1F
→
07/21 20:17, , 2F
07/21 20:17, 2F
→
07/21 20:19, , 3F
07/21 20:19, 3F
推
07/22 00:30, , 4F
07/22 00:30, 4F
→
07/22 09:15, , 5F
07/22 09:15, 5F
討論串 (同標題文章)
本文引述了以下文章的的內容：
完整討論串 (本文為第 2 之 2 篇)：