我正在尝试寻找该递归的时间复杂度:
T(n) = 2T(n1/2) + log n
我已经非常接近解决方案了,但是遇到了障碍。我需要解决:
n(1/2k) = 1
以简化我的替换模式。我不是在寻找递归的答案,只是要解决k的问题。
T(n) = 2T(n1/2) + log n
我已经非常接近解决方案了,但是遇到了障碍。我需要解决:
n(1/2k) = 1
以简化我的替换模式。我不是在寻找递归的答案,只是要解决k的问题。
对于k,n>1的情况下,任何非零的x都有nx>1,所以无法解决以下方程:
n(1/2k) = 1
唯一的解法是选取一个k,使得1 / 2k = 0,但这是不可能的。
然而,你可以解决以下方程:
n(1/2k) = 2
首先,将两边取对数:
(1 / 2k) lg n = lg 2 = 1
接着,将两边乘以2k:
lg n = 2k
最后,再次取对数:
lg lg n = k
因此,当k = lg lg n时,这个递归停止。
虽然你只要求k的值,但因为已经过去了一年,我想指出你可以进行变量替换来解决这个问题。尝试设置k = 2n。那么k = lg n,因此你的递归就是:
T(k) = 2T(k / 2) + k
这个解法(使用主定理)是T(k) = Θ(k log k),并且使用k = lg n的事实,整个递归的解为Θ(log n log log n)。
希望这可以帮到你!
兄弟,如果这是快速排序方程:
这个问题的解决方案是 O(n*log(n))
,因为现在它甚至更小了(T(n) ~ n^1/2
),对于一些N
,这意味着你的复杂度小于O(n*log(n))
。
尝试使用归纳法证明你的界限。
以任何底数为基数的对数1,其结果都为0。
因此
n^((1/2)^k) = 1
log(n)(n^((1/2)^k)) = log(n)(1)
1/2^k = 0
log(1/2)((1/2)^k) = log(1/2)(0)
以0为基数的对数是负无穷...所以...
k = -无穷大。
我认为你应该使用一个不同于1的“最终数字”来代替n,只是这样说而已...
k
的问题,你会得到一些令人惊恐的东西。 - harold