PTT數位生活區 / Prob_Solve (計算數學 Problem Solving)

Re: [問題] 兩題複雜度求解

看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (-858993460)時間14年前 (2010/06/04 02:36)推噓0(0推 0噓 0→)

留言0則, 0人參與討論串2/3 (看更多)

※ 引述《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)