recursion - 如何求解递归关系 T(n)=T(n^1/2)+n

Question

T(n)=T(n^1/4)+n^1/2+n T(n^1/8)+n^1/4+n^1/2+n 。.

 T(n^1/2^k)+n^1/k-1+n^1/k-2......+n
 I got k= loglog(n) but i am not able to solve the series by putting this k value into above series.

标签： recursion

Answer 1

首先代入 n = 2^m 给我们

T(2^m) = T(2^(m-1)) + 2^m

现在让 S(m) = T(2^m)。这大大简化了递归关系

S(m) = S(m/2) + 2^m

根据主定理，

S(m) = O(2^m)

最后，

T(n) = T(2^m) = S(m) = O(2^m) = O(2^(log_2 n)) = O(n)。