Re: [問題] 兩題複雜度求解
※ 引述《FRAXIS (喔喔)》之銘言：
: T(n) = n^0.5 T(n^0.5) + n^0.5
: 假設n = 2^2^k
: T(n) = n^0.5 * (n^0.25 T(n^0.25) + n^0.25) + n^0.5
: = n^(1-2^-k) T(0) + n^0.5 + n^0.75 + ....
: 這邊我解不出closed form
這樣吧:
依然令 n = 2^2^k
T(n) = 2^2^(k-1) T(2^2^(k-1)) + 2^2^(k-1)
= 2^2^(k-1) [ 2^2^(k-2) T(2^2^(k-2)) + 2^2^(k-2) ] + 2^2^(k-1)
= (2^2^(k-1)*2^2^(k-2)) T(2^2^(k-2)) + (2^2^(k-1)*2^2^(k-2)) + 2^2^(k-1)
= ...
k-1 k-1 k-1
= T(2) Π 2^2^i + Σ Π 2^2^i (中間有點繁故略,
i=0 j=0 i=j 但再展一層就可看出是此模式
是 T(2) 而非 T(0) 也可由此看出)
k-1 k-1
然後 Π 2^2^i = 2^(Σ 2^i) = 2^(2^k-2^j) = 2^2^k / 2^2^j
i=j i=j
所以「T(2)的係數」為 2^2^k / 2^2^0 = 2^2^k / 2 (上式令 j=1)
k-1 k-1 k-1
常數項為 Σ 2^2^k / 2^2^j = 2^2^k Σ 1/2^2^j < 2^2^k Σ 1/2^j
j=0 j=0 j=0
= 2^2^k (2 - 1/2^(k-1)) < 2^2^k * 2
(那個小於是由於 2^x > x 對所有 x 都成立)
也就是常數項也是 2^2^k 乘上一個小於 2 的數 c
那麼全式就成了 T(n) = 2^2^k (T(2)/2+c) = n (T(2)/2+c) = O(n)
--
順帶一提, 事實上這個 c 值在 k→∞ 時的極限值為
∞
Σ 1/2^2^j ≒ 0.8164215090218931...
j=0
http://www.research.att.com/~njas/sequences/A007404
--
第二題我再慢慢想....orz
--
**** 說:
不要期望一個精神力差不多已經見底的人阿Orz
--
※ 發信站: 批踢踢實業坊(ptt.cc)
◆ From: 140.112.30.84
※ 編輯: LPH66 來自: 140.112.30.84 (06/04 02:56)
討論串 (同標題文章)