asymptotic-complexity - 通过归纳证明递归函数的复杂性

Question

我需要通过归纳证明——

T(n) = T(n-1) + c2 , T(1) = c1 

The run time complexity is - T(n) = O(n)

在基本案例和归纳假设之后的归纳步骤中，我写道 -

T(k+1) = T(k) + c2 = O(k) + c2 = O(k + 1)

但是为了证明这个运行时间复杂度，我需要证明存在 C,N0 > 0 所以最终的不等式是正确的。

如果有人能告诉我如何找到/或纠正我的归纳。谢谢。

Answer 1

要通过归纳证明，您必须执行三个步骤。

1. P(n)为 n定义命题

2. showP(n_0)对于基本情况是正确的n_0

3. 假设这P(k)是真的并且显示P(k+1)也是真的

似乎您没有具体的定义P(n)。

所以让P(n) := there exists constant c(>0) that T(n) <= c*n.

你的归纳步骤将是这样的：

假设这P(k)是真的。然后P(k+1) = T(k) + c2

由P(k), there exists constant c_k(>0) that T(k) <= c_k*k.

所以T(k+1) = T(k) + c2 <= c_k*k + c2 <= (c_k+1)*k + (c_k+1) = (c_k+1)*(k+1)（如果我们选择c_k+1 = max(c_k, c2)）

也是如此P(k+1)。

因此，这些通过归纳证明

for every n > n_0=1, there exists constant c(>0) that T(n) <= c*n.

PS 在这里你可以得到一些关于感应的读数。此外，在 MIT OCW，课程6042J为归纳和强归纳提供了很好的讲座，您可以练习并获得直觉。