我目前正在观看关于算法的 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 进行归纳,上面的证明是不正确的,但是为什么?
最佳答案
您可以对 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
。
关于algorithm - 为什么 Induction 总是不适用于 Big-O?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/25459490/