algorithm - 如何解决这个递归关系: T(n) = 4*T(sqrt(n)) + n

Question

我知道如何使用 Master Method 解决递推关系。 我也知道如何解决以下重复问题:

T(n) = sqrt(n)*T(sqrt(n)) + n

T(n) = 2*T(sqrt(n)) + lg(n)

在上面的两个递归中，递归树的每一层都有相同的工作量。并且递归树中一共有log log n层。

我在解决这个问题时遇到了麻烦: T(n) = 4*T(sqrt(n)) + n

编辑: 这里 n 是 2 的幂

Answer 1

假设 n = 2^k。我们有 T(2^k) = 4*T(2^(k/2)) + 2^k。让 S(k) = T(2^k)。我们有 S(k) = 4S(k/2) + 2^k。通过使用 Mater Theorem，我们得到 S(k) = O(2^k)。由于 S(k) = O(2^k) 和 S(k) = T(2^k)，T(2^k) = O(2^k) 这意味着 T(n) = O(n)。