作者LPH66 (-858993460)
看板Prob_Solve
标题Re: [问题] 两题复杂度求解
时间Fri Jun 4 02:36:46 2010
※ 引述《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)