这个递归算法的大O是多少？

Question

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

一种算法可以递归地解决大小为n-1的子问题，并对解决方案进行线性量的工作。

我尝试使用“插入并计算”方法并发现大O是n，线性的，但这似乎不正确。我还能尝试什么？

- hopelessmuffins

---

每个项都是线性的，那么1 + 2 + 3 + ... + n就是线性的吗？ - John Coleman

Answer 1

数学堆栈交换的人可能比我做得更好，但我会尝试一下。

算法的描述不太清楚，所以有两种可能性：

1. 该算法对每个子问题执行固定量的工作。在这种情况下，算法实际上将在O(n)时间内运行（技术上是2n，但忽略常数因素）。
2. 该算法对每个子问题执行线性数量的工作。在这种情况下，您正在查看一个线性循环，每次执行线性工作。n次执行，每次执行n个单位的工作= O(n^2)。显然，每次后续执行的工作量都会减少，这将表现为递归关系解决方案中的大约T(n) = (1/2)n^2，假设我记得该模式的问题正确。

- Mac O'Brien

---

问题的措辞似乎暗示了第二种解释（算法在 n-1 上调用自身，然后对“解决方案”进行线性数量的工作，这表明递归调用后有线性数量的工作）。 - John Coleman

Answer 2

您提到的递归公式如下：

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

这意味着：

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

因此，该算法的复杂度为 O(n²)。

- displayName