divide-and-conquer - 求解 T(n) = 2T(n/2) + log n

Question

我正在尝试解决 T(n) = 2T(n/2) + log n

替换 n = 2^k

T(2^k) = 2T(2^(k-1)) + k  
T(2^k) = 2^2 T(2^(k-1)) + 2(k-1) + k

after k steps
T(2^k) = 2^k T(1) + 2^(k-1) + 2 * (2^(k-2)) +....+k

所以基本上我需要对 i*2^i 的一项求和，其中 i = 1 以记录 n - 1。
我找不到一种简单的方法来总结这些项。难道我做错了什么 ？有没有其他方法可以解决这个递归？掌握定理对她有用吗？如果是，比如何？

谢谢。

Answer 1

Wolfram|Alpha 给出了一个封闭形式的解：

对于由初始条件固定的常数 c_1。

顺便说一下，log(n)/log(2) = lg(n)，其中 lg 是以二为底的对数。

Answer 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); i=2,3,4...k 其中 g(1) = T(1)/2 = c;

然后您可以在其中展开 sum 表达式并定义它 = y; 然后展开y/2的表达式；yy/2 是几何级数，所以可以求解

正如我所计算的，总和 = 3/2 - (k+2)/2^k;

所以 T(n) = 2^k * g(k) = (3/2+c)*n - (2+logn)