7

我知道关系 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 的基本定义。

4

4 回答 4

13

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

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

n 是一个函数，Ο(1) 是一组函数。数字也不是（归纳证明就是一举证明一大堆单独的数字）。等号的使用，如 n = Ο(1)，是 f ∈ Ο(1) 的非正式简写，其中 f(x) = x。

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

  • 通过假装 n 是一个数字（归纳过程中的下一个数字）而不是整个函数
  • 通过假装等号意味着两个数字相等，这就是归纳证明中的含义，而不是 element-of 的简写

如果您想更清楚地了解此证明失败的原因，请将 n 替换为函数的另一种表示法 f（其中 f(x) = x），并在需要时将等号替换为 element-of 符号，并查看证明是否仍然成立感觉。

基本情况：

让 h(x) = 1 英寸
          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) 是否无关，因为这些函数的行为彼此非常非常不同。

于 2010-10-03T20:28:34.310 回答
6

大 O 符号是关于函数的，所以像这样的语句1 = O(1)没有意义。您在这里证明的是，如果您采用任意n且恒定的函数，f(x) = n那么f = O(1)这是正确的并且没有矛盾。证明没有问题，问题是您将常量函数f(x) = n与函数混淆了f(n) = n。对于后者，我们有这个f = O(n)，如果你尝试用你的方法来证明它，你会发现它不起作用。

于 2010-09-26T11:38:50.307 回答
3

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

一个例子是

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

通过简单的数学，上面的陈述意味着 O(n) = 0 不是。所以我想说不要为此使用 MI。MI 更适合绝对值。

于 2010-09-26T10:24:29.400 回答
0

如果你需要做任何涉及 Big-O 表示法的严格证明，你需要从Big-O 的格式定义开始。在一个你不能只说的证明中O(1) + 1 = O(1)。您需要根据正式定义进行证明。要证明一个函数（f(n) = n例如）是 O(1)，您需要找到与定义匹配的唯一 x0 和 M。您可以通过归纳来证明这一点，也可以使用定义进行矛盾证明来证明f(n) = n不是O(1)

正如 Olathe 在他的回答中所说，您不能只添加 Big-O 集和函数。从将函数分类为特定 Big-O 集的成员的正式定义开始。

于 2010-10-03T20:48:11.143 回答