递归关系

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 在限制中。