first you should define a recursive export,say T(1) then: since T(2^k) = 2T(2^(k-1)) + k; * we define g(k) = T(2^k)/2^k; then * come into: g(k) = g(k-1) + k/2^k = g(1) + sum(i/2^i); i=2,3,4...k where g(1) = T(1)/2 = c;
where you could then unfold the sum expression and define it = y; then unfold the expression of y/2; y-y/2 is a geometric progression, so youcan solve it
发布评论
评论（2）
首先你应该定义一个递归导出，比如 T(1)
然后：
因为 T(2^k) = 2T(2^(k-1)) + k; *
我们定义 g(k) = T(2^k)/2^k；
然后 * 进入：
g(k) = g(k-1) + k/2^k = g(1) + sum(i/2^i);我=2,3,4...k
其中 g(1) = T(1)/2 = c；
然后您可以在其中展开求和表达式并定义它 = y;
然后展开y/2的表达式；
yy/2是等比级数，所以你可以
按照我的方法求解，sum = 3/2 - (k+2)/2^k;
所以 T(n) = 2^k * g(k) = (3/2+c)*n - (2+logn)
first you should define a recursive export,say T(1)
then:
since T(2^k) = 2T(2^(k-1)) + k; *
we define g(k) = T(2^k)/2^k;
then * come into:
g(k) = g(k-1) + k/2^k = g(1) + sum(i/2^i); i=2,3,4...k
where g(1) = T(1)/2 = c;
where you could then unfold the sum expression and define it = y;
then unfold the expression of y/2;
y-y/2 is a geometric progression, so youcan solve it
as I worked out, sum = 3/2 - (k+2)/2^k;
so T(n) = 2^k * g(k) = (3/2+c)*n - (2+logn)
Wolfram|Alpha给出一个封闭形式的解决方案：
表示由初始条件固定的常量 c_1。
顺便说一下，log(n)/log(2) = lg(n)，其中 lg 是以 2 为底的对数。
Wolfram|Alpha gives a closed form solution:
for a constant c_1 that is fixed by the initial condition.
By the way, log(n)/log(2) = lg(n), where lg is the base two logarithm.