→ Murasaki0110:前面用等比公式 後面用sigma 10/07 15:35
→ doom8199:[T(n/2)]^4 ...? 看原po的代入結果好像沒有那個4次方 10/07 17:54
→ kaocoming:這題既視感好重 是作業吧...... 10/17 02:04
T(n) = 8^n[T(n/2)]^4 + 4^n T(1) = 1
T(n) = theta(?)
用代入法
T(n) = 8^(n + n/2 + n/4 + ... + n/(2^k-1)) T(1)^4
+ 8^(n + n/2 + n/4 + ... + n/(2^k-2))4^(n/2^k-1)+ ... +8^n4^n/2+4^n
感覺答案已經呼之欲出，但是後面那一串要怎麼化成closed form?
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 118.166.100.19