divide-and-conquer - 重复关系

Question

任何人都可以用以下等式帮助解决分而治之算法的递归关系吗？我很确定你不能在这里使用主定理，因为它不是 T(n/b) 的形式，但可能在这里忘记了一个简单的数学规则。请帮忙。

T(n)=T(√n)+logn。

Answer 1

请注意，对于一些k>0我们有

T(n) = log n + log n^{1/2} + log n^{1/4} + ... + log n^{1/2^k} =
     = log n + (1/2)*log n + (1/4)*log n + ... + (1/k) * log n
     = (1 + 1/2 + 1/4 + ... + 1/2*k) log n
     = (1 + 2^{-1} + 2^{-2} + ... + 2^{-k})log n
     <= 2 log n

它由此得出T(n) = O(log n)。因为在极限中，所以边界<= 2 log n跟随。1+1/2+1/4+1/8+1/16+...=2