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

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)) + c*m
       <= 2*( 2*T((2^(m/2))^(1/2)) + c*log2(2^(m/2)) ) + c*m
        = 4*T(2^(m/4)) + 2*c*m
       <= 4*( 2*T((2^(m/4))^(1/2)) + c*log2(2^(m/4)) ) + 2*c*m
        = 8*T(2^(m/8)) + 3*c*m
       <= ...
        = (2^log2(m))*T(2^1) + log2(m)*c*m
        = m*T(2) + c*m*log2(m)
        = log2(n)*T(2) + c*log2(n)*log2(log2(n))
        = O(log2(n)*log2(log2(n)))

术语 log2(m) 源于这样一个事实，即我们在每个新的递归级别将 m 除以二，因此在 [= 之前最多需要 log2(m) 次除法19=].

现在，如果 n 不是 2 的幂，您会注意到存在一些数字 r，它是 2 的幂，使得 n <= r < 2*n。然后你可以写 T(n) <= T(r) = O(log2(r)*log2(log2(r))) = O(log2(2*n)*log2(log2(2*n))) = O(log2(n)*log2(log2(n))).

所以总体答案是

T(n) = O(log2(n)*log2(log2(n)))

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

Time complexity of the following recurrence equation?

algorithm

time-complexity

big-o

recurrence