如何解决:T(n)= T(n - 1)+ n

Question

我得到以下结论:

T(n) = T(n - 1) + n = O(n^2)

现在,当我解决这个问题时,我发现边界非常宽松.我做错了什么或是这样吗？

Answer 1

您还需要一个基于重复关系的基础案例.

T(1) = c
T(n) = T(n-1) + n

要解决这个问题,您可以先猜测一个解决方案,然后使用归纳法证明它是有效的.

T(n) = (n + 1) * n / 2 + c - 1

首先是基础案例.当n = 1时,根据需要给出c.

对于其他n:

  T(n)
= (n + 1) * n / 2 + c - 1
= ((n - 1) + 2) * n / 2 + c - 1
= ((n - 1) * n / 2) + (2 * n / 2) + c - 1
= (n * (n - 1) / 2) + c - 1) + (2 * n / 2)
= T(n - 1) + n

所以解决方案有效.

要获得猜测,请注意当c = 1时,您的递归关系会生成三角形数字:

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

直观地,三角形大约是正方形的一半,并且在Big-O表示法中,常数可以被忽略,因此O(n ^ 2)是预期的结果.

Answer 2

可以这样想：
在递归的每次“迭代”中，您都会执行 O(n) 的工作。
每次迭代都有 n-1 项工作要做，直到 n = 基本情况。（我假设基本情况是 O(n) 工作）
因此，假设基本情况是与 n 无关的常数，则递归的迭代次数为 O(n) 。
如果每次都有 n 次 O(n) 迭代，则 O(n)*O(n) = O(n^2)。
你的分析是正确的。如果您想了解有关这种解决递归方法的更多信息，请查看递归树。与其他方法相比，它们非常直观。