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

Question

关闭。这个问题是off-topic .它目前不接受答案。












想改善这个问题吗？ Update the question所以它是 on-topic对于堆栈溢出。

10年前关闭。




Improve this 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 gives a closed form solution :





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

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