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

Question

我已经解决了以下问题：

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

现在我计算出来的结果发现这个界限非常宽松。我是做错了什么还是本来就是这样的？

- Tony The Lion

---

我投票关闭此问题，因为它是一个数学问题，而不是一个编程问题。 - Raymond Chen

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..

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

- Mark Byers

---

你能告诉我你在答案中得出第三个方程式的方法吗？你应用了什么数学技巧？ - Tony The Lion

@Tony：这只是一个“猜测”。实际上，我知道三角数公式——我并没有真正的猜测它，我已经知道了答案。通常比起从基本原理推导答案，更容易先“猜测”正确的答案并证明其正确性。这是解决递归关系的标准技术。 - Mark Byers

@Tony：一个受过教育的猜测的技术术语是"Ansatz"。参见：http://en.wikipedia.org/wiki/Ansatz。在维基百科上有一些关于使用猜测来解决递归关系的信息：http://en.wikipedia.org/wiki/Recurrence_relation。其他可能的递归关系求解方法也在那里列出。 - Mark Byers

从O(n^2)可以更容易地猜测出精确解是一个二次多项式ax^2+bx+c，并解出a、b和c。在Knuth、Oren、Patashnik的书《Concrete Mathematics》中有详细的描述如何解决这类问题。 - starblue

Answer 2

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

- Rubys

---

我认为我太过于沉迷于数学，忘记了我们正在处理递归的事实。也许这就是我不太理解的原因。对于上述问题，我得到了T(n) <= 2n，这是否正确？ - Tony The Lion

我不太明白你在问什么，上面有很多内容。 - Rubys

@Tony：不，那不正确。对于小的n，T(n)可以大于2n。 - Mark Byers

Answer 3

这个问题的解决方案很简单。您需要展开递归：

T(n) = T(n-1) + n = T(n-2) + (n - 1) + n = 
= T(n-3) + (n-2) + (n-1) + n = ... =
= T(0) + 1 + 2 + ... + (n-1) + n 

你在这里有一个等差数列，其总和为1/2*n*(n-1)。从技术上讲，你在这里缺少边界条件，但是通过任何常数边界条件，你可以看到递归是O(n^2)。

- Salvador Dali

Answer 4

看起来还不错，但取决于基本情况T(1)。假设您将执行n个步骤以将T(n)转换为T(0)，每次n项都在0和n之间，平均为n/2，因此n * n / 2 =（n^2）/ 2 = O(n^2)。

- shuttle87