作者realturner (rt)
看板b95902HW
标题[作业] 演算法 T(n) = T(a*n) + T(b*n) + g(n) 复杂度证明
时间Tue Nov 6 11:10:21 2007
如题，在
T(n) = T(a*n) + T(b*n) + g(n) , n>=n0
T(n) = c , n<n0
其中 1>a>b>0, g(n) = θ(n)
的递回式中，我可以处理後得到
sigma{ g(a^α*b^β) }
可以被
sigma{ c1(a+b)^k, k=0,1,...p1 }, sigma{ c2(a+b)^k, k=0,1,...p2 }
这两个包住，其中 c1, c2 为二正常数
p1, p2 都会是 θ(log n )
但是，当我想处理 T(n) 递回展开的常数项 T(n) = c 的部份时出了问题....
我要找的是特定的 (i,j) 集合可以满足 (a^i)(b^j)n 刚刚好小过 n0
然後算出集合的大小，定为 M
则常数所造成的 complexity 就是 M*c = θ(M),
M 会是一个和 n, a, b, n0 有关的函数
以上看似ok ，但是我却不知道要如何说明 M = θ(n)...
有强者可以看得出来吗@@
--
※ 发信站: 批踢踢实业坊(ptt.cc)
◆ From: 140.112.91.5