algorithm - 通过主定理解决递归关系？

Question

有人可以再澄清一下这个解决方案吗？

T(n) = 2T(n^1/2) + log n

解决方案：

令 k = log n，

T(n) = T(2^k)=2T(2^(k/2)) + k

代入方程 S(k) = T(2^k)

我们明白了

S(k)=2S(k/2) + k

现在，这个递推方程允许我们使用主定理，它指定

S(k) 是 O(k log k)。代回 T(n) 意味着 T(n) 是 O(log n log log n)

Answer 1

你能把 n 除以 2 多少次？Log_2(n) 次。因为 Log_2(n) 是你需要提高 2 才能获得 n 的幂。

此外，loglog(n) 是您可以取 n 的平方根的次数，所以如果您知道这一点，那么也许这种替换不是必需的。