complexity-theory - 使用归纳法证明 n = Big-O(1)

Question

我知道关系 n = Big-O(1) 是错误的。但是如果我们使用包含 Big-O 的归纳法，它可以被证明。但谬误是我们不能引入 Big-O。但我的问题是我们如何通过使用常量来反驳这种关系。

假证明就在这里，请用常量给我证明它是假的。我对常量感到困惑，我不知道证明中使用的每个关系是否具有不同的常量或相同的常量。请就题目指教。

TO prove: n= O(1)
for n=1 , 1= O(1) proved

归纳假设:让它为真:n-1 = O(1)
现在我们证明 n = O(1)

LHS :  n = (n-1) + 1 
         =  O(1) + 1
         =  O(1) + O(1)
         =  O(1) 

假证..
我想澄清 <= 和常量方面的谬误，即 Big-O 的基本定义。

Answer 1

这里隐藏着一个巨大的逻辑谬误:

LHS : n = (n-1) + 1
= O(1) + 1
= O(1) + O(1)
= O(1)

n 是一个函数，而 Ο(1) 是一组函数。数字也不是(归纳证明都是关于一口气证明一大堆单个数字的东西)。使用等号，如 n = Ο(1), is an informal shorthand for f ∈ Ο(1), where f(x) = x .

本证明使用 the fallacy of equivocation有两种方式:

通过假设 n 是一个数字(归纳过程中的下一个数字)而不是整个函数

假装等号意味着两个数相等，这就是归纳证明中的意思，而不是元素的速记

如果你想更清楚地看到这个证明失败的原因，用另一个函数的符号 f(其中 f(x) = x)替换 n，并在需要的地方用元素符号替换等号，看看证明是否仍然感觉。

基本情况:

让 h(x) = 1 in
h ∈ Ο(1) [任何函数都在 Ο(那个函数)]

感应案例:

n = (n - 1) + 1 [代数恒等式]
n - 1 = n - 1 [算术]

让 f(x) = x
g(x) = f(x) - 1 英寸
g ∈ Ο(1) [假设 g ∈ Ο(1) 因为不同的函数 h 是]
f ∈ Ο(1 + 1) [根据 Ο 的定义]
f ∈ Ο(2) [算术]

很明显，这根本不是归纳证明。它本身甚至不是一个有效的证明，因为我们只证明了 h ∈ Ο(1)，这与是否 g ∈ Ο(1) 无关，因为这些函数的作用非常非常不同。