[理工] 演算法 Recurrence Relation

看板Grad-ProbAsk作者 (code)時間13年前 (2012/10/07 14:36), 編輯推噓0(0推 0噓 3→)
留言3則, 3人參與, 最新討論串1/1
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
→
10/07 15:35, , 1F
前面用等比公式 後面用sigma
10/07 15:35, 1F
→
10/07 17:54, , 2F
[T(n/2)]^4 ...? 看原po的代入結果好像沒有那個4次方
10/07 17:54, 2F
→
10/17 02:04, , 3F
這題既視感好重 是作業吧......
10/17 02:04, 3F
‣ 更多 TNC 的文章
文章代碼(AID): #1GSIBe_m (Grad-ProbAsk)