使用归纳法证明函数的时间复杂度

Question

我想通过归纳f(n) = 0找出这个函数的时间复杂度，if n = 0

f(n) = f(n − 1) + 2n − 1，如果 n ≥ 1 我使用方法调用重复替换，那么我找到了 f(n)

的近似形式

f(n)= f(n − 1) + 2n − 1 =f(n-2)+4n-4 =f(n-3)+6n-8 .... =f(n-i )+2^in-d

然后通过取 i=n 我得到 f(n)=f(0)+2^(n+1)-d 并且可以得出结论它的时间复杂度为 O(2^n)因为 f(0) 和 d 都是常量。

然而我发现答案应该是 O(n^2)，我哪里做错了

Answer 1

你的数学有误。

f(n) = f(n - 1) + 2n - 1
f(n) = f(n - 2) + 4n - 4
f(n) = f(n - 3) + 6n - 9
...
f(n) = f(n - i) + 2i n - i^2

当 i = n 你有：

f(n) = f(n - n) + 2n n - n^2
     = f(0) + (2 - 1) n^2
     = n^2

因此，f(n)是O(n^2)

然而你错了。这不是函数的时间复杂度，它是 O(n)，因为它有多少次递归，这是函数的顺序，这意味着 "quickly it diverges"。 O(n^2) 表示函数以二次速率发散。

Answer 2

我没有完全理解这个问题。计算值的复杂度是O(n)，因为你可以从0开始计算：

f(0) = 0
f(1) = 0 + 2*1 - 1 = 1
f(2) = 1 + 2*2 - 1 = 4
f(3) = 4 + 2*3 - 1 = 9

实际上，您可能明白了。 . .第 n 个值是 n^2。我在问题的上下文中猜测这就是他们想要的答案。但是，要计算它似乎是 O(n).

Using induction to prove time complexity of functions