递归关系：解决T(n-1)的大O问题

Question

我正在解决一些与大O相关的递归关系问题，到目前为止，我只遇到了涉及以下形式的递归关系：

T(n) = a*T(n/b) + f(n)

对于上述内容，我很容易找到大O符号。但是最近我遇到了以下方程：

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

我不太确定如何解决这个大O符号的问题。实际上，我已经尝试将方程式输入以下内容：

T(n) = T(n-1) + 2
T(n-1) = T(n-2)
T(n-2) = T(n-3)

我不确定这是否正确，但我遇到了问题，需要一些帮助。谢谢！

- Parth

Answer 1

假设 T(1) = 0。

T(n) = T(n-1) + 2
 = (T(n-2) + 2) + 2
 = T(n-2) + 4
 = (T(n-3) + 2) + 4
 = T(n-3) + 6
 = T(n-k) + 2k

将k设为n-1，你就有

T(n) = 2n - 2

因此，它的时间复杂度为O(n)。

- Andreas Jansson

---

@AndreasJansson 我不明白你在前两步中的代数运算。你声称 $T(n-1) + 2 = (T(n-2) + 2) + 2$，但我不知道你是怎么得出这个结论的。问题中没有任何提示，你怎么能做出这样的假设呢？如果 $T(2) = 10000000000000000$，我们并不知道，那你怎么能假设它不是呢？ - user1174868

@ripDaddy69 如果我们将(n-1)代入原始的T(n)中，我们得到 T(n-1) = T(n-2) + 2。对吧？现在如果我们在第一行用T(n-2)+2替换T(n-1)，我们就得到了第二行。 - Brian

Answer 2

由于问题已经得到解答，让我补充一些有关如何找到递归复杂度背后的直觉。

主定理只适用于“分而治之”类型的递归，例如 T(n) = a*T(n/b) + f(n)，其中 a 是子问题的数量，每个子问题的大小为原始问题的 1/b。但是递归 T(n) = T(n-1) + 2 在技术上并没有将问题“分割”成子问题，因此主定理在这里不适用。

如果我们仔细观察递归，很明显它需要执行 n 步，每步都需要常数时间，本例中为 2。因此复杂度将为 O(n)。

我特别发现第二个直觉对于大多数递归非常有帮助（可能不是全部）。例如，你可以尝试类似递归 T(n) = T(n-1) + n 的相似情况，其复杂度当然为 O(n^2)。

- Nasir

Answer 3

T(n) = 2*n = 2*(n-1)+2 = T(n-1)+2

因此T(n) = 2*n，这意味着O(n)

- Chaos