algorithm - 如何求解：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)。
你的分析是正确的。如果您想了解有关这种解决递归方法的更多信息，请查看递归树。与其他方法相比，它们非常直观。

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

Answer 4

看起来不错，但将取决于基本情况 T(1)。假设您将执行 n 个步骤以使 T(n) 变为 T(0)，并且每次 n 项在 0 和 n 之间的任何地方，平均为 n/2，因此 n * n/2 = (n^2)/2 = O(n^2)。