作者Honor1984 (奈何上天造化弄人？)
看板Math
標題Re: [其他] 演算法通解的推導
時間Wed Nov 10 01:53:02 2021
※ 引述《renine14 ()》之銘言：
: 想請問下面當lambda不等於1時怎麼推導出下面的通解呢？
: https://i.imgur.com/cQbR1nj.jpg
: https://i.imgur.com/7ORDXPd.jpg
n/q萬一是分數怎麼辦？
你一定是有些條件背景沒有寫清楚
T(n) = pT(n/q) + cn^d ，λ = (q^d)/p，T(0) = α
= (p^m)T(n/(q^m)) + c(n^d)[λ/(1-λ)][(1/λ)^m - 1] 當λ =/= 1
(p^m)T(n/(q^m)) + c(n^d)m 當λ = 1
若n = q^k
則到k = (log_q)n時就可終止了
當λ = 1 有T(n) = (p^k)α + c(n^d)k = αn^d + c(n^d)(log_q)n ~ O(n^d * log_q n)
當λ =/= 1
T(q^k) = pT(q^(k-1)) + c(q^k)^d，令Q(k) = T(q^k)
=> Q(k) = pQ(k-1) + c(pλ)^k，Q(0) = α
=> Q(k) = T(q^k) = αp^k + c[λ/(1-λ)][(pλ)^k - p^k]
=> T(n) = αn^((log_q)p) + c[λ/(1-λ)][n^d - n^((log_q)p)]
~ O(n^d) 當d > (log_q)p
~ O(n^((log_q)p)) 當d < (log_q)p
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 114.24.154.165 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/Math/M.1636480384.A.23B.html
1F：→ Honor1984 : 第一航算式T(1) = α，筆誤 11/10 02:12
2F：→ Honor1984 : 當d = (log_q)p ，顯然T(n) ~ O(n^d) 11/10 02:56