доказать 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. </p>

Answer 1

Здесь скрыта огромная логическая ошибка:

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

n - это функция, а Ο (1) - это набор функций.Ни одно из них не является числом (а индукционные доказательства - это доказательство всего множества отдельных чисел одним махом).Использование знаков равенства, таких как n = Ο (1), , является неофициальным сокращением для f ∈ Ο (1), где f (x) = x .

В этом доказательстве используется ошибка двусмысленности двумя способами:

• , притворяясь, что n - это число (следующее число в индуктивном путешествии), а не целая функция
• отпритворство в знаке равенства означает, что два числа равны, что и означает в доказательстве индукции, а не является сокращением для элемента * из 1015 *

Если вы хотите более четко понять, почему это доказательство не удается, замените 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, что не так. Так что я бы сказал, не используйте МИ для этого. МИ больше подходит для абсолютных значений.

Answer 4

Если вам нужно сделать какие-либо строгие доказательства, связанные с обозначением Big-O, вам нужно начать с определения формата Big-O в формате . В доказательстве вы не можете просто сказать O(1) + 1 = O(1).Вы должны сделать доказательство с точки зрения формального определения.Чтобы доказать, что функция (например, f(n) = n) есть O (1), вам нужно найти уникальные x0 и M, которые соответствуют определению.Вы можете продемонстрировать это посредством индукции, и вы также можете сделать доказательство от противного, используя определение, чтобы показать, что f(n) = n не O(1)

Так же, как Олат заявил в своем ответе,Вы не можете просто добавить наборы и функции Big-O.Начните с формального определения того, что классифицирует функцию как член определенного набора Big-O.