如何求解：T(n) = T(n - 1) + n
我已经解决了以下问题：
T(n) = T(n - 1) + n = O(n^2)
现在，当我解决这个问题时，我发现界限非常松散。我是否做错了什么，或者只是这样？
I have the following worked out:
T(n) = T(n - 1) + n = O(n^2)
Now when I work this out I find that the bound is very loose. Have I done something wrong or is it just that way?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（4）
您还需要一个递归关系的基本情况。
为了解决这个问题，您可以首先猜测一个解决方案，然后使用归纳法证明它是有效的。
首先是基本情况。当 n = 1 时，这给出了所需的 c。
对于其他 n：
所以该解决方案有效。
为了首先进行猜测，请注意，当 c 时，您的递归关系会生成三角形数字 = 1：
直观上，三角形大约是正方形的一半，并且在 Big-O 表示法中，可以忽略常数，因此 O(n^2) 是预期结果。
You need also a base case for your recurrence relation.
To solve this, you can first guess a solution and then prove it works using induction.
First the base case. When n = 1 this gives c as required.
For other n:
So the solution works.
To get the guess in the first place, notice that your recurrence relationship generates the triangular numbers when c = 1:
Intuitively a triangle is roughly half of a square, and in Big-O notation the constants can be ignored so O(n^2) is the expected result.
这样想吧：
在递归的每次“迭代”中，您都会执行 O(n) 工作。
每次迭代都有 n-1 项工作要做，直到 n = 基本情况。 （我假设基本情况是 O(n) 工作）
因此，假设基本情况是与 n 无关的常数，则递归迭代次数为 O(n)。
如果每次都有 n 次 O(n) 迭代，则 O(n)*O(n) = O(n^2)。
你的分析是正确的。如果您想了解有关这种解决递归方法的更多信息，请查看递归树。与其他方法相比，它们非常直观。
Think of it this way:
In each "iteration" of the recursion you do O(n) work.
Each iteration has n-1 work to do, until n = base case. (I'm assuming base case is O(n) work)
Therefore, assuming the base case is a constant independant of n, there are O(n) iterations of the recursion.
If you have n iterations of O(n) work each, O(n)*O(n) = O(n^2).
Your analysis is correct. If you'd like more info on this way of solving recursions, look into Recursion Trees. They are very intuitive compared to the other methods.
对于这个问题来说，解决方案非常简单。您必须展开递归：
这里有算术级数，总和为 1/2*n*(n-1)。从技术上讲，您在这里缺少边界条件，但对于任何恒定的边界条件，您都会看到递归是
O(n^2)。The solution is pretty easy for this one. You have to unroll the recursion:
You have arithmetic progression here and the sum is
1/2*n*(n-1). Technically you are missing the boundary condition here, but with any constant boundary condition you see that the recursion isO(n^2).看起来差不多正确，但取决于基本情况 T(1)。假设您将执行 n 个步骤来获得 T(n) 到 T(0)，并且每次 n 项介于 0 和 n 之间，平均值为 n/2，因此 n * n/2 = (n^2)/2 = O(n^2)。
Looks about right, but will depend on the base case T(1). Assuming you will do n steps to get T(n) to T(0) and each time the n term is anywhere between 0 and n for an average of n/2 so n * n/2 = (n^2)/2 = O(n^2).