以下递归方程的时间复杂度？

Question

嗨，我在计算以下递归方程的复杂度时遇到问题：

   T(n)={ O(1)                    ,  if n<=2  
        { 2*T(n^(1/2)) + O(logn)  ,  if n>=2 

我得出了O（2 ^ n * nlogn）的可能结论。如果有人有任何线索，我会很高兴。谢谢。

Answer 1

现在假设n > 2是2的幂，因此您可以写入n = 2^m。还让我们在O(log(n))项中将常量明确写为c*log2(n)。

然后，解开递归给我们：

T(2^m) <= 2*T((2^m)^(1/2)) + c*log2(2^m)
        = 2*T(2^(m/2)) + m
       <= 2*( 2*T((2^(m/2))^(1/2)) + c*log2(2^(m/2)) ) + c*m
        = 4*T(2^(m/2)) + c*m + c*(m/2)
       <= ...
        = (2^log2(m))*T(2^1) + c*m +c*(m/2) + c*(m/4) + ... + c*(m/(2^log2(m)))
        = m*T(2) + c*m +c*(m/2) + c*(m/4) + ... + c*(m/(2^log2(m)))

log2(m)是由于我们在每个新的递归级别上将m除以​​2，所以在log2(m)之前将（最多）进行m <= 1除。

现在让我们最后处理这笔长款项。这简直等于

c*m*(1/2 + 1/4 + ... +1/(2^log2(m))

并且您可能知道，（C0]的大小等于（1/2）的k一阶幂的和永远不会达到1（只需使用公式对几何中的数字求和进步，如果你想说服自己）。因此，该项小于k。

所以把事情放回原处：

c*m = c*log2(n)

现在，如果n不是2的幂，则可以注意到存在某个数r，它是2的幂，因此n <= r <2 * n。然后您可以写T(n) = T(2^m) <= m*T(2) + c*log2(n) = log2(n)*T(2) + c*log2(n) = O(log2(n)). 。

所以总的答案是

T(n) <= T(r) = O(log2(r)) = O(log2(2*n)) = O(log2(n))