如何求解：T（n）= T（n-1）+ n [英] How to solve: T(n) = T(n - 1) + n

问题描述

我得出以下结论：

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的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！