使用迭代法解决递归关系问题

Question

如何使用迭代方法解决 T(n) = T(n-1) + n，答案为 theta(n^2)

- Santhosh

Answer 1

T(n) = T(n-1) + n = T(n-2) + n-1 + n = ... = 1+ 2 + ... + n = (n+1)n/2 = theta(n^2)

注意假设T(0) = 0（递归必须有基础）
希望这是你的意思

- amit

Answer 2

有时候，你也可以使用特征方程法来解决递归关系。这涉及到确定特定积分和总解。

更多信息请参见：解决递归关系

- user668269