如何求解：T(n) = T(n - 1) + n

我已经解决了以下问题：

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

现在，当我解决这个问题时，我发现界限非常松散。我是否做错了什么，或者只是这样？

您还需要一个递归关系的基本情况。

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

所以该解决方案有效。

为了首先进行猜测，请注意您的递归关系会生成三角数 http://en.wikipedia.org/wiki/Triangular_number当c=1时：

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

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