[理工] [DS]-兩題time complexity
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)
→
07/21 16:15, , 1F
07/21 16:15, 1F
→
07/21 16:16, , 2F
07/21 16:16, 2F
→
07/21 20:06, , 3F
07/21 20:06, 3F
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：