作者doom8199 (～口卡口卡 修～)
看板Grad-ProbAsk
标题Re: [理工] [algo]-求closed form
时间Sat Jan 2 22:44:16 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..不知道该怎麽求..麻烦指导一下，感谢。
---
这类递回式我都用凑的 ＝.＝
型如 T(n) = aT(n/2) + k(n) , a 属於R
想法就是先设法凑成 [T(n) - f(n)] = a[T(n/2) - f(n/2)] 的型态
所以只要找出 f(n) , 就能解得 T(n)
可是若展开後比较系数, 会发现:
f(n) - af(n/2) = k(n)
这个式子刚好就是我们欲求的 XD
所以正常来说， T(n) 只能根据 k(n) 的型态
case by case 的去解它
---
T(n) = 2T(n/2) + log(n) (令底为2)
不防先假设 T(n) + a*log(n) = 2*[ T(n/2) + a*log(n/2) ] ___(1)
→ T(n) = 2T(n/2) + alog(n) - 2a
这时会发现比较系数後 a=1
但却多了常数项 -2a = -2 , 无法消除
所以就大胆假设 "特解" 也有常数项
即重令: T(n) + a*log(n) + b = 2*[ T(n/2) + a*log(n/2) + b]
→ T(n) = 2T(n/2) + alog(n) - 2a + b
比较系数後可知: ┌ a = 1 → ┌ a = 1
└ -2a + b = 0 └ b = 2
所以原式可改写成:
T(n) + f(n) = 2*[T(n/2) + f(n/2)] with f(n) = log(n) + 2
----
有了上式，就能导出一般式:
不仿令 n = 2^r
所以 T(n) + f(n) = 2*[T(n/2) + f(n/2)]
= 2^(r) * [T(1) + f(1)]
= n[T(1) + 2]
即 T(n) = n[T(1) + 2] - f(n)
= T(1)*n + 2n-log(n) - 2
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.113.141.151