关闭。这个问题是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。
我找不到一种简单的方法来总结这些术语。难道我做错了什么 ?有没有其他方法可以解决这个递归问题?掌握定理对她有用吗?如果是比怎么样?
谢谢。
最佳答案
Wolfram|Alpha gives a closed form solution :
对于由初始条件固定的常数 c_1。
顺便说一下,log(n)/log(2) = lg(n),其中 lg 是以二为底的对数。
关于divide-and-conquer - 求解 T(n) = 2T(n/2) + log n,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/7592931/