¿Cómo pruebo o refuto lo siguiente?
implica
- ¿Por qué una máquina Turing puede ejecutar todos los algoritmos informáticos?
- ¿La función de módulo es distributiva, asociativa o conmutativa? Explicar con ejemplos y pruebas. ¿Cómo uso este concepto en la programación competitiva?
- ¿Podría el basilisco de Roko realmente suceder?
- ¿A qué escuela debo asistir para un programa de posgrado de matemáticas: Stony Brook o UIUC?
- Como una niña india de 23 años, he completado mi licenciatura en tecnología. Me interesa la fotografía y la quiero como mi profesión. ¿Hay alguna forma de convencer a mi papá? ¿Qué tengo que hacer?
?
Nunca me gustó usar la igualdad junto con la notación big-O. Se usa en los artículos wiki, pero usar la igualdad en situaciones como esta es engañoso. Cuando dices que una cosa está en un conjunto determinado por la otra, no debes decir que una es igual a ese conjunto determinado por la otra.
Cambiando la notación, ahora tenemos la pregunta
¿Cómo pruebo o refuto lo siguiente: si [matemática] f [/ matemática] es [matemática] o (g) [/ matemática] entonces [matemática] f [/ matemática] es [matemática] \ matemática O (g) [ /mates]?
Vamos a desempaquetar la declaración. Tome la conclusión big-O. Asumiremos que ambas funciones tienen un valor positivo, ya que ese es siempre el caso cuando se observa el crecimiento de las funciones. La declaración [math] f [/ math] es [math] \ mathcal O (g) [/ math] dice informalmente que [math] f [/ math] no es mucho más grande que [math] g [/ math]. Más precisamente, dice que para valores grandes de [matemática] x [/ matemática], [matemática] f (x) [/ matemática] está delimitada por algún múltiplo de [matemática] g (x) [/ matemática], es decir , hay algún número [matemática] M [/ matemática] para que
[matemáticas] \ qquad f (x) \ leq M g (x) [/ matemáticas]
para valores suficientemente grandes de [math] x [/ math].
Ahora tome la hipótesis little-o. Para que [matemática] f [/ matemática] sea [matemática] o (g) [/ matemática], [matemática] f [/ matemática] tiene que ser mucho más pequeña que [matemática] g [/ matemática] en el siguiente sentido preciso : la relación [matemática] f (x) / g (x) [/ matemática] se aproxima a 0 cuando [matemática] x [/ matemática] se acerca al infinito:
[matemáticas] \ qquad \ displaystyle \ lim_ {x \ to \ infty} \ frac {f (x)} {g (x)} = 0 [/ matemáticas]
Ahora, ¿es cierto que si esa relación se aproxima a 0, entonces [matemática] f [/ matemática] finalmente está limitada por un múltiplo de [matemática] g [/ matemática]? Sí. Aquí hay una prueba.
Si la relación se aproxima a 0, eso significa que para cualquier [matemática] \ epsilon [/ matemática] positiva hay algo de [matemática] N [/ matemática], de modo que para valores grandes de [matemática] x [/ matemática]
[matemáticas] \ qquad \ dfrac {f (x)} {g (x)} <\ epsilon [/ matemáticas]
Tome [math] \ epsilon = 1 [/ math]. Entonces para grandes [matemáticas] x [/ matemáticas]
[matemáticas] \ qquad \ dfrac {f (x)} {g (x)} <1 [/ matemáticas]
Por lo tanto, para grandes [matemáticas] x [/ matemáticas], tenemos [matemáticas] f (x) <g (x) [/ matemáticas]. Entonces, sí, de hecho, [math] f [/ math] finalmente está limitado por [math] g [/ math] en sí.
Eso significa que ser una pequeña función es una condición más fuerte que ser una gran función.
