我试图找到重复的时间复杂度：
T(n) = 2T(n 1/2 ) + log n
我非常接近解决方案，但是，我遇到了障碍。我需要解决：
n (1/2 k ) = 1
为 k 简化我的替换模式。我不是在寻找复发的答案，只是寻找k.
问问题
18378 次
4 回答
7
当你开始展开递归时，你会得到：
这里有一些额外的步骤：
现在使用递归的边界条件（数字 2 选择为 0 和 1 没有意义），您将得到：
代k回方程式，您将得到：
这里有几个使用相同想法的递归。
于 2015-12-15T07:04:58.737 回答
3
不可能解决
n (1/2 k ) = 1
对于 k，因为如果 n > 1，那么对于任何非零 x， n x > 1。解决这个问题的唯一方法是选择 k 使得 1 / 2 k = 0，但这是不可能的。
但是，您可以解决此问题：
n (1/2 k ) = 2
首先，取双方的日志：
(1 / 2 k ) lg n = lg 2 = 1
接下来，将两边乘以 2 k：
lg n = 2 k
最后，再记录一次：
lg lg n = k
因此，一旦 k = lg lg n，这种重复就会停止。
尽管您只询问了 k 的值，但自从您询问以来已经整整一年了，我想我会指出您可以进行变量替换来解决这个问题。尝试设置 k = 2 n。然后 k = lg n，所以你的递归是
T(k) = 2T(k / 2) + k
这（使用主定理）求解到 T(k) = Θ(k log k)，并且使用 k = lg n 这一事实，整体递归求解为 Θ(log n log log n)。
希望这可以帮助！
于 2013-10-26T05:52:33.720 回答
0
老兄，如果它是等式的快速排序：
解决方案是O(n*log(n))因为现在它甚至更小（T(n) ~ n^1/2），N这意味着您的复杂性小于O(n*log(n)).
尝试使用归纳法来证明你的界限
于 2012-10-27T20:34:56.787 回答
0
日志基数为 1，为 0。
所以
n^((1/2)^k) = 1
对数(n)(n^((1/2)^k)) = 对数(n)(1)
1/2^k = 0
对数（1/2）（（1/2）^k）=对数（1/2）（0）
对数基数为 0 的任何值都是负无穷大......所以......
k = -无穷大。
我认为你应该为 n 使用不同的“最终数字”，而不是 1 只是说......
于 2012-10-27T20:52:25.073 回答