作者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