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