Re: [其他] 時間複雜度的證明題兩題
※ 引述《jj811208 (UML)》之銘言：
: 不好意思，這其實是我的作業，我今年大三，跨系選了資工系的演算法，
: 可總覺得用到的數學成分有點重，而經過google後，依然無法自行解題，
: 想把這些題目放上來這邊，請教各位大大，這兩題的算法。
: 跪求orz~
: http://imgur.com/kyG5gym
第一題
for n a power of b => n = b^r, r 為 0 or 正整數
T(b^r) = aT(b^(r-1)) + (b^r)^c
T(1) = K
令F(r) = T(b^r)
F(r) = aF(r-1) + (b^r)^c
設F(r-p) = aF(r-(p-1)) + b^((r-p)c) 為 (p-th) 式
r-1
=> Σ (p-th) a^p
p=0
r-1
=> F(r) = (a^r)F(0) + Σ[b^((r-p)c) * a^p]
p=0
=> T(n) = Ka^((log_b)n) + n^c[(a/b^c)^((log_b)n) - 1]/[a/(b^c) - 1]
= Ka^((log_b)n) + n^c[b^c/[a - b^c]][(a/b^c)^((log_b)n) - 1]
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
第二題
T(n) = n^(1/2)T(n^(1/2)) + n
T(m) = K
m = n^[(1/2)^i]
n = m^(2^i)
令F(p) = T(n^[(1/2)^p]) , p 為 0 或 正整數
p
令g(p) = Σ(1/2)^t
t=1
設F(p) = n^((1/2)^(p+1))F(p+1) + n^((1/2)^(p)) 為 (p-th) 式
i-1
=> Σ (p-th) * n^[(1/2)^p]
p=0
i-1
=> F(0) = n^g(i) F(i) + n + Σn^[g(p) + (1/2)^p]
p=1
i-1
=> T(n) = n^[1 - (1/2)^i] K + n + Σn
p=1
= n^[[2^i - 1]/(2^i)] + in
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.56.10.112
※ 文章網址: https://www.ptt.cc/bbs/Math/M.1490065505.A.32C.html
推
03/21 12:33, , 1F
03/21 12:33, 1F
討論串 (同標題文章)
