使用归纳证明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 = 0(1),是f∈(1)的非正式简写,其中f(x)= x.

这个证明以两种方式使用模棱两可的谬误:

• 通过假装n是一个数字(归纳旅程中的下一个数字)而不是整个函数
• 通过假装等号来表示两个数字是相等的,这就是它在感应证明中的含义,而不是元素的简写.

如果你想更清楚地看到为什么这个证明失败了,用一个函数的另一个符号替换n,f(其中f(x)= x),并且在需要的地方用符号元素替换等号,看看证据是否仍然有效感.

基本情况:

let h(x) = 1 in
          h ∈ Ο(1)        [Any function is in Ο(that function)]

归纳案例:

          n = (n - 1) + 1 [Algebraic identity]
      n - 1 = n - 1       [Arithmetic]

let f(x) = x
    g(x) = f(x) - 1 in
          g ∈ Ο(1)        [Assume g ∈ Ο(1) because a different function, h, was]
          f ∈ Ο(1 + 1)    [By definition of Ο]
          f ∈ Ο(2)        [Arithmetic]

更清楚的是,这根本不是感应证据.它本身甚至都不是一个有效的证明,因为我们只证明了h∈Ο(1),它与g∈Ο(1)无关,因为这些函数的作用非常非常不同.

Answer 2

大O符号是关于函数的,所以语句1 = O(1)没有意义.你在这里证明的是,如果你采取任意n和常数函数,f(x) = n那么f = O(1)这是真的并且没有矛盾.证明没有问题,问题是您将常量函数f(x) = n与函数混淆f(n) = n.对于后者,我们有这个f = O(n),如果你试图用你的方法证明它,你会发现它不会起作用.

Answer 3

这里你必须理解的一件事是 Big-O 或简称 O 表示函数增长的“速率”。您不能使用数学归纳法来证明此特定属性。

一个例子是

O(n^2) = O(n^2) + O(n)

通过简单的数学计算，上述语句意味着 O(n) = 0，但事实并非如此。所以我想说不要为此使用 MI。MI 更适合绝对值。