6

我正在为 Big O 解决一些递归关系问题，到目前为止，我只遇到了涉及这种形式的递归关系：

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

对于上述内容，我很容易找到大 O 符号。但我最近被抛出一个带有以下等式的曲线球：

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

我不太确定如何为 Big O 解决这个问题。我实际上已经尝试插入如下等式：

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

我不完全确定这是否正确，但我被困住了，需要一些帮助。谢谢！

4

3 回答 3

20

假设 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)

于 2010-07-11T18:55:24.497 回答
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)。

于 2016-08-18T05:22:23.693 回答
0

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

所以 T(n) = 2*n 这意味着 O(n)

于 2010-07-11T18:56:36.053 回答