La Notación Big O "es el elemento de la" o "es igual"

Question

La gente siempre está teniendo problemas con las "grandes $O$" notación cuando se trata de cómo escribirlo de una manera matemáticamente correcta.

Ejemplo: usted tiene dos funciones $n\mapsto f(n) = n^3$ $n\mapsto g(n) = n^2$

Obviamente $f$ es asintóticamente más rápido que $g$. Es $f(n) = O (g(n))$ o es $f(n) \in O(g(n))$?

Mi profe dice que el primero está mal, pero es una práctica muy común, por lo tanto se usa muy offten en los libros. Aunque la segunda es la de la derecha.

¿Por qué es eso así?

Answer 1

Me gusta mucho la Wikipedia nota de esto:

La declaración "$f(x)$ $O(g(x))$ " [ ... ] se suele escribir como $f(x) = O(g(x))$. Algunos consideran que se trata de un abuso de notación, ya que el uso del signo igual puede ser engañoso, ya que sugiere una simetría que esta declaración no tiene. Como de Bruijn dice, $O(x) = O(x^2)$ es verdad, pero de $O(x^2) = O(x)$ no lo es. Knuth describe las declaraciones tales como "igualdad", ya que si los lados podría ser revertido, "podríamos deducir ridículo cosas como $n = n^2$ de las identidades $n = O(n^2)$$n^2 = O(n^2)$."

Por estas razones, sería más preciso establecer la notación y escribir $f(x) \in O(g(x))$, el pensamiento de $O(g(x))$ como la clase de todas las funciones $h(x)$ tal que $|h(x)| \leq C|g(x)|$ para algunas constantes $C$. Sin embargo, el uso del signo igual es habitual. Knuth señaló que "los matemáticos que habitualmente uso el $=$ señal, ya que el uso de la palabra 'es' en inglés: Aristóteles es un hombre, pero un hombre no es necesariamente Aristóteles."

Answer 2

El uso de $\in$ -teóricamente correcto, pero un inconveniente. Por ejemplo, $$ \sin x = x - \frac{x^3}{3} + \mathrm O(x^5) $$ En este caso, $\mathrm O$ debe ser interpretado como existe una $\mathrm O(x^5)$ función para realizar esta igualdad válida. El $=$ notación también permite la notación asintótica a aparecer en ambos lados y hacer operaciones aritméticas: $$ e^x + \mathrm S(x) = \mathrm O(e^x) $$ En este caso, para cada $\mathrm O(x)$ función en la izquierda, existe un $\mathrm O(e^x)$ función en la derecha para hacer de esto una igualdad.

Answer 3

$O(g(x))$ es una clase de funciones - piense en ello como una "propiedad" de las funciones que puede tener. Por el literal interpretación del signo igual, "$f(x) = O(g(x))$" debe interpretarse como "$f$ es literalmente igual a una cierta clase de funciones." Pero las funciones y las clases de funciones son diferentes tipo de cosas - incluso si esto era lo que quería decir, es como decir que un particular, apple es igual a una cesta de manzanas. Pero, ¿qué nos referimos cuando decimos "$f(x) = O(g(x))$" es que $f$ pertenece a la clase de funciones $O(g(x))$ - lo, $f(x) \in O(g(x))$.

La razón por la que el uso de $=$ en lugar de $\in$ es debido a que, dada la particular de los usos de la grande -$O$ (notación y poco-$o$ notación, si usted está familiarizado con eso) $=$ es enormemente más conveniente. Decimos cosas como $x^3 + O(x) = O(x^3)$, por ejemplo; no queremos decir que $O(x)$ es un objeto que puede ser añadido a $x^3$, o que, cuando la adición se hace realmente hacemos la clase de funciones $O(x^3)$, acabamos de decir que para cualquier función de $f \in O(x)$, la función de $x^3 + f(x)$ es un miembro de $O(x^3)$. Pero si yo quería escribir que en más estándar de notación, yo tendría que decir algo como $\{x^3 + f(x) \mid f(x) \in O(x)\} \subseteq O(x^3)$. Este es un inconveniente para escribir y difícil de leer, así que prefiero el "resbaladizo" la notación $x^3 + O(x) = O(x^3)$.

Sin embargo, no estoy seguro de que me diría que frases como $f(x) = O(g(x))$ están mal. Por convención, son perfectamente correctas - es sólo que cuando una expresión incluye $O$ (o $o$), $=$ no significa lo que significa. Eso está bien.

Answer 4

Con respecto a $=$ ser más útil o conveniente de $\in$ debido a que permite cosas como $x^3 + O(x) = O(x^3)$, parece que para eso puedes usar $x^3 + O(x) \subseteq O(x^3)$. Esto parece más preciso para mí, porque significaría "cada elemento del conjunto a $x^3 + O(x)$ es un elemento del conjunto a $O(x^3)$." creo que es exactamente lo que uno quiere decir. (donde $g+A:=\{g+f:f\in A\}$ e al $g$ es una función de y $A$ es un conjunto de funciones, y de manera similar para situaciones similares.)

Hacer la declaración con el subconjunto es mencionado por Reese respuesta, pero creo que la definición de la suma de una función y un conjunto de funciones, y también la suma de series de funciones, en la forma sencilla elimina los inconvenientes de decir las cosas como $\{x^3+f(x)∣f∈O(x)\}\subseteq O(x^3)$. (La definición de las cosas de igual manera, con la multiplicación, y la aplicación de las funciones en general.)

Cuando las cosas se definen de esta manera, que debería ser tan simple como el uso de $\in$ en lugar de $=$ cuando hay una sola función en la izquierda, y el uso de $\subseteq$ en lugar de $=$ cuando hay un conjunto de funciones de la izquierda, y parece más preciso.

Answer 5

Aquí está mi cinco centavos que vale la pena: Si vemos una declaración de la forma $$f(x)=g(x)+O\bigl(p(x)\bigr)\qquad(x\to\xi)$$ a continuación, para cada una de las $x$ el valor exacto de la expresión $O\bigl(p(x)\bigr)$ es definido por esta ecuación:$:=f(x)-g(x)$. Además se nos dice que hay una constante $C>0$ tal que para todos los $x$ en un adecuado perforado barrio de $\xi$ esta diferencia es $\leq C\bigl|p(x)\bigr|$.