作者nowar100 (拋磚引玉)
看板Grad-ProbAsk
標題[理工] [DS]-time complexity
時間Tue Jul 21 15:14:10 2009
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)，是怎麼算出來的 @@
謝謝 ^^
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.113.93.39
※ 編輯: nowar100 來自: 140.113.93.39 (07/21 15:41)
1F：→ gorocky:第二題利用EXTENDED MASTER METHOD公式就可以求出 答案 07/21 16:15
2F：→ gorocky:n(lgn)^2 07/21 16:16
3F：→ nowar100:謝謝 07/21 20:06