问题描述
我得出以下结论：
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?
推荐答案
这样想：
在递归的每个迭代中，您都进行O（n）工作。
每个迭代都有n-1个工作要做，直到n =基本情况。 （我假设基本情况是O（n）的工作）
因此，假设基本情况是n的常数，则递归有O（n）个迭代。 $ b如果每个O（n）工作有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.
这篇关于如何求解：T（n）= T（n-1）+ n的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持！