如何求解：T（n）= T（n-1）+ n

我有以下解决方案：

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

现在，当我解决这个问题时，我发现界限非常松散。我做错了什么吗？

这样想：

在递归的每个“迭代”中，您都要进行O（n）工作。

每次迭代都有n-1个工作要做，直到n =基本情况为止。（我假设基本情况是O（n）的工作）

因此，假设基本情况是n的常数，则递归有O（n）个迭代。

如果每个O（n）工作有n次迭代，则O（n）* O（n）= O（n ^ 2）。

您的分析是正确的。如果您想了解有关解决递归的更多信息，请查看递归树。与其他方法相比，它们非常直观。