推 assassin88:阿這..兩個人答案不一樣= = 我沒正解XDD 01/04 15:29
※ 編輯: FRAXIS 來自: 140.119.162.50 (01/04 15:42)
→ FRAXIS:分解的時候有點小問題 我改了答案 01/04 15:43
※ 引述《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