probar n = Big-O (1) usando la inducción

Question

Sé que la relación n = Big-O (1) es falsa. Pero si usamos la inducción que involucra a Big-O, puede probarse. Pero la falacia es que no podemos inducir a Big-O. Pero mi pregunta es cómo podemos refutar la relación usando las constantes.

La prueba falsa está aquí, por favor deme la prueba de que es falsa usando las constantes. Estoy confundido con las constantes, no sé si cada relación utilizada en la prueba tiene constantes diferentes o lo mismo. Por favor ilumine sobre el tema. hipótesis

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

inducción: que es cierto: n-1 = O (1) ahora demostramos que n = O (1)

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

falsamente demostró .. Quiero la aclaración de la falacia en términos de < = y constantes, eso es en la definición básica de Big-O.

Answer 1

Una cosa que tienes que entender aquí es que Big-O o simplemente O denota la 'tasa' a la que crece una función. No puede usar la inducción matemática para probar esta propiedad en particular.

Un ejemplo es

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

Por simple matemática, la declaración anterior implica O (n) = 0, lo que no lo es. Entonces yo diría que no use MI para esto. MI es más apropiado para valores absolutos.

Answer 2

La notación O grande se trata de funciones, por lo que las declaraciones como 1 = O(1) no tienen ningún significado. Lo que está demostrando aquí es que si toma un n arbitrario y la función constante f(x) = n entonces f = O(1) que es verdadero y no da ninguna contradicción. No hay problema con la prueba, el problema es que está confundiendo la función constante f(x) = n con la función f(n) = n. Para este último tenemos ese f = O(n) y si intentas probarlo con tu método, verás que no funcionará.

Answer 3

Hay una enorme falacia lógica oculta aquí:

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

n es una función y Omicron y; (1) es un conjunto de funciones. Ninguno de los dos es un número (y las pruebas de inducción tienen que ver con probar cosas para un montón de números individuales de una sola vez). El uso de signos iguales, como n = & Omicron; (1), is an informal shorthand for f ∈ Ο(1), where f(x) = x.

Esta prueba utiliza the fallacy of equivocation de dos maneras:

• pretendiendo que n es un número (el número siguiente en el viaje inductivo) en lugar de una función entera
• simulando los signos iguales significan que dos los números son iguales, que es lo que significa en una prueba de inducción, en lugar de ser una abreviatura de element-of

Si quiere ver más claramente por qué falla esta prueba, reemplace n con otra notación para una función, f (donde f (x) = x), y los signos iguales con elementos de signos donde sea necesario y ver si la prueba todavía tiene sentido.

Caso base:

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

caso inductivo:

 
      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] 

Se vuelve mucho más claro que esto no es una prueba de inducción en absoluto. Ni siquiera es una prueba válida en sí misma, porque solo probamos que h ∈ y Omicron; (1), que no tiene nada que ver con si g ∈ y Omicron; (1), ya que esas funciones actúan muy, muy diferente entre sí .

Answer 4

Si necesita realizar pruebas rigurosas que impliquen la notación Big-O, debe comenzar con format definition of Big-O En una prueba, no puede simplemente decir O(1) + 1 = O(1). Necesita hacer la prueba en términos de la definición formal. Para demostrar que una función (f(n) = n por ejemplo) es O (1), necesita encontrar x0 y M únicos que coincidan con la definición. Usted puede demostrar esto a través de la inducción, y también se puede hacer una prueba por la contradicción mediante la definición de demostrar que no es f(n) = nO(1)

Así como Olathe afirma en su respuesta, no se puede simplemente añadir conjuntos de Big-O y funciones Comience con la definición formal de lo que clasifica una función como miembro de un determinado conjunto Big-O.