algorithm - 为什么 Induction 总是不适用于 Big-O？

Question

我目前正在观看关于算法的 ocw 视频类(class)，在第二堂课中我停留在教授通过归纳法证明以下陈述的地方:-

n=O(1)

proof:-    

For base case    
1=O(1)    
suppose n-1 = O(1)    
=> 1+(n-1)=O(1)+O(1)     
=> n=O(1).    
hence it is proved.    

但是教授告诉我们不能对大 O 进行归纳，上面的证明是不正确的，但是为什么？

Answer 1

您可以对 Big-O 进行归纳，但是当 n 是变量而不是常量时，给定的归纳过程是不正确的。

当您编写 1 = O(1) 时，解释为

if f_1(n) = 1 for all n then f_1(n) = O(1)

这是正确的。

现在如果我们为所有n定义f_a(n) = a，那么通过归纳我们可以证明f_a(n) = O(1) 对于所有 a，这也是正确的。

但是，如果 n 不是常量而是变量，则您无法通过归纳得到 n = O(1)，因为没有 k 这样 f_k(n) = n 对于所有 n。