作者FRAXIS (喔喔)
看板Grad-ProbAsk
标题Re: [理工] [algo]-求closed form
时间Mon Jan 4 12:28:26 2010
※ 引述《assassin88 (AI)》之铭言：
: T(n) = 2T(n/2) + lgn
: = 4T(n/4) + 3lgn - 2
: = ...
: = 2^kT(n/2^k) + (2^k-1)lgn + ???
: 後面常数像求不出closed form..不知道该怎麽求..麻烦指导一下，感谢。
假设 n = 2^k
T(n) = 2T(n/2) + lgn
= 4T(n/4) + lgn + 2(lgn - 1)
= 8T(n/8) + lgn + 2(lgn - 1) + 4(lgn - 2)
= nT(1) + lgn + 2(lgn -1) + ... n/2
令S(n) = lgn + 2(lgn - 1) + ... n/2
2S(n) = 2lgn + 4(lgn -1) + ... n
2S(n) - S(n) = -lgn + 2 + 4 + 8 + ... + n
S(n) = 2n - 2 - lgn
T(n) = nT(1) + 2n - lgn - 2
应该是这样，希望没算错..
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.119.162.50
1F：推 assassin88:阿这..两个人答案不一样= = 我没正解XDD 01/04 15:29
※ 编辑: FRAXIS 来自: 140.119.162.50 (01/04 15:42)
2F：→ FRAXIS:分解的时候有点小问题 我改了答案 01/04 15:43