如何解决：t（n）= t（n -1） + n

Question

我已经解决了以下内容：

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

现在，当我解决这个问题时，我发现界限很松。我做错了什么还是那样做？

Answer 1

这样想：
在递归的每个“迭代”中，您可以做O（n）工作。
每次迭代都有N-1工作要做，直到N =基本情况。 （我假设基本案例是o（n）工作）
因此，假设基本情况是n的恒定独立性，则存在递归的O（n）迭代。
如果您有o（n）的局部工作，则o（n）*o（n）= o（n^2）。
您的分析是正确的。如果您需要有关解决递归方式的更多信息，请查看递归树。与其他方法相比，它们非常直观。

Answer 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

因此解决方案有效。

首先要猜测，请注意您的复发关系会生成 三角数 当C = 1：

T(1) = 1:

*

T(2) = 3:

*
**

T(3) = 6:

*
**
***

T(4) = 10:

*
**
***
****

etc..

直观地，三角形大约是正方形的一半，在大符号中，常数可以忽略，因此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 * n/2 =（n^2）/2 = o（n^2）。