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 ) の略記です。

この証明は、次の2 つの方法で、不平等の誤謬を使用します。

  • n が関数全体ではなく数字 (帰納的な旅の次の数字) であるふりをすることによって
  • 等号のふりをすることによって、2 つの数が等しいことを意味します。これは、帰納法の証明で意味することであり、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) [別の関数 h があったので g ∈ Ο(1) と仮定]
          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

ここで理解しなければならないことの 1 つは、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)。形式的な定義の観点から証明を行う必要があります。関数 (たとえば) が O(1) であることを証明するにはf(n) = n、定義に一致する一意の x0 と M を見つける必要があります。これは帰納法で証明できますし、定義を使用して矛盾による証明を行って、そうでないことを示すこともできますf(n) = n。O(1)

Olathe が回答で述べたように、Big-O セットと関数を追加することはできません。関数を特定の Big-O セットのメンバーとして分類するものの正式な定義から始めます。

于 2010-10-03T20:48:11.143 に答える