作者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/cn.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