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

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 求平方根的次数，所以如果您知道这一点，那么替换可能不是那么必要。