Mi opinión sobre esta anotación coincide con el comentario de David Speyer. Como señala la respuesta de Henning, nuestras respuestas son sólo formas diferentes de ver la misma cosa. A menudo recurro a reglas similares a las suyas como definición operativa, pero me parece que mi enfoque es más fácil de motivar.
Procedemos en dos pasos: (a.) entender una expresión que implica la notación asintótica, y (b.) entender el uso del signo de igualdad en esta notación.
Regla de interpretación de las expresiones. Toda expresión (bien formada) que implique funciones y operaciones estándar (e..g, ${ +, \times, -, \div, \exp, \log }$ ) y las notaciones asintóticas $\{ O, o, \Omega, \omega, \Theta\}$ corresponde a un conjunto de funciones. [Para simplificar, nos limitaremos sólo a la $O$ anotación]. Este conjunto se construye de forma recursiva exactamente como cabría esperar: $$ \begin{align*} E_1 \circ E_2 &:= \{ f(n) \circ g(n) \quad : \quad f(n) \in E_1, g(n) = E_2 \}, \quad \circ \in \{ +, \times, -, \div \}; \\ \Psi (E) &:= \{ \Psi(f(n)) \quad : \quad f(n) \in E \}, \quad \Psi \in \{ \exp, \log \}. \\ \end{align*} $$ Esta interpretación de las expresiones es perfectamente natural; es análoga a la Suma de Minkowski de dos conjuntos, ampliado para operaciones más generales. Incluso podemos enriquecer esto con una regla un poco más complicada para $O$ :
$$ O(E) := \bigcup_{f(n) \in E} O(f(n)). $$
Estas reglas no son completas; hay que añadir los casos base apropiados cuando $E$ , $E_1$ y $E_2$ son funciones únicas y no un conjunto de funciones. El caso base más interesante es la expresión $O(f(n))$ que se define exactamente igual que en el post. Como punto final, podemos acordar la identidad de una única función $f(n)$ con el conjunto $\{ f(n) \}$ Esto resulta ser muy conveniente en la práctica.
Por ejemplo, una expresión de la forma $5 + O(n) + O(n^2)\log(O(n^3))$ representa el conjunto $$ \{ 5 + f(n) + g(n) \log h(n) \ : \ f(n) \in O(n), \quad g(n) \in O(n^2), \quad h(n) \in O(n^3) \}. $$ Del mismo modo, podemos interpretar la expresión como $O(2^{n^2 + O(n)})$ aplicando el $O(\cdot)$ regla dos veces.
Reglas de interpretación del signo de igualdad. Cuando se afirma que $E_1 = E_2$ donde $E_1$ y $E_2$ son conjuntos representados por expresiones como la anterior, se debe interpretar siempre que $E_1 \subseteq E_2$ . Por ejemplo, $$5 + O(n) + O(n^2)\log(O(n^3)) \ \color{Red}{=} \ O(n^2\log n)$$ es en realidad una abreviatura de $$5 + O(n) + O(n^2)\log(O(n^3)) \ \color{Red}{\subseteq} \ O(n^2\log n) .$$
Además, está el caso $f(n) = E$ ; por ejemplo, $n = O(n^2)$ . En este caso, podemos identificar la función $f(n)$ con el conjunto $\{ f(n) \}$ y aplicar la interpretación anterior. Esto nos dice que $f(n) = E$ es lo mismo que decir $f(n) \in E$ (porque $f(n) \in E \iff \lbrace f(n) \rbrace \subseteq E$ ).
Podría decirse que esto no es natural, ya que choca fuertemente con la interpretación estándar del signo igual como igualdad (de conjunto). De hecho, se trata de una dificultad inherente, ya que cabría esperar que cualquier definición razonable de igualdad para ser simétrica: $$ E_1 = E_2 \quad \stackrel{\color{Red}{(??)}}{\implies} \quad E_2 = E_1. $$ Sin embargo, como todos sabemos, esto rara vez es cierto con la notación asintótica. Por tanto, la única salida parece ser anular la noción intuitiva de igualdad en favor de otra menos natural. [En este punto, cabe señalar que las reglas de Henning también recurren a redefinir adecuadamente el signo de igualdad].
Una muestra de propiedades. Muchas reglas comúnmente utilizadas para manipular la notación asintótica se derivan directamente de la interpretación anterior. Como caso de estudio, considero algunas de las propiedades ya estudiadas por Henning en su respuesta:
-
"Ámbito local" o Cambio de significado . Por ejemplo, en $O(n) + O(n) = O(n)$ se pueden sustituir las distintas funciones $f(n)$ , $g(n)$ y $h(n)$ . La definición de " $+$ " en la interpretación del conjunto de funciones se basa claramente en esta idea.
-
La notación asintótica es no es simétrico . Por ejemplo, $O(n) = O(n^2)$ mientras que $n^2 \stackrel{\color{Red}{?}}{=} O(n)$ es falso. Esto es por la misma razón que la inclusión de conjuntos no lo es.
-
Sin embargo, es transitivo es decir, si $E_1 = E_2$ y $E_2 = E_3$ entonces $E_1 = E_3$ . Esto se deduce simplemente de la transitividad de la inclusión de conjuntos.
Palabras finales. Una de las principales quejas contra la notación asintótica parece ser que no suele ser simétrica, como implica el signo de igualdad. Esto es legítimo, pero en este caso, el verdadero problema es el abuso del signo igual, más que la idea de las funciones como conjuntos. De hecho, que yo recuerde, todavía no he encontrado un solo uso de la notación asintótica que sea técnicamente incorrecto, incluso después de sustituir mentalmente el signo igual por $\in$ o $\subseteq$ según corresponda.
