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