algorithm - 如何递归求解 T(n) = 5T(n/2) + n^2, T(1) = 2

Question

如何在不使用主定理的情况下获得 T(n) = 5T(n/2) + n^2, T(1) = 2 的渐近上界。

这是我的步骤，但我不知道如何处理最后的求和，因此无法找到这个递归函数的大 O 答案。

T(n) = 5T(n/2) + n^2
     = 5^2 T(n/2^2) + 5(n/2)^2 + n^2
     = 5^3 T(n/2^3) + 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
     = ...
     = 5^i T(n/2^i) + 5^i(n/2^i)^2 + ...+ 5^2(n/2^2)^2 + 5(n/2)^2 + n^2
     = 5^i T(n/2^i) + n^2 Sum of k from 0 to i, (5/4)^k

如何处理求和？谢谢。

标签： algorithmrecursionbig-o

Answer 1

如何处理求和？

您在总和中描述的是几何级数[wiki]。这种形式的总和：

 n
---
\     i
/    a
---
i=0

有一个已知的解决方案：

 n
---           n+1
\     i      a    - 1
/    a     = --------
---            a - 1
i=0

所以这里是你的总和：

k 从 0 到 i 的总和，(5/4)^k

等于：

4 * ((5/4)^(i+1) - 1)

我们知道它i仅限于log ₂ n，这应该足以解决方程。