recursion - 这个递归算法的大O是什么

Question

我们有一个大小为n的问题

递归求解大小为 n − 1 的子问题并执行的算法解决方案的线性工作量。

我尝试使用 plug n chug，发现 big-O 是 n，线性的，但这对我来说似乎不正确。我还能尝试什么？

Answer 1

你提到的递归公式是:

• T(n) = T(n-1) + O(n)

这意味着:

T(n) = kn + k(n-1) + k(n-2) + .. + k，等于 k ​​ n * (n + 1)/2。

所以，算法的复杂度为O(n²)。