16 de junio de 2018
La notación de la \(O\) mayúscula (big O notation o símbolo de Landau) es una es un concepto matemático que nos permite,
a grandes rasgos, describir la velocidad de crecimiento de una función al acotar esté por medio de otra función delimitadora (asíntota).
Es miembro de la familia de notaciones conocidas como notaciones de Bachmann-Landau o notaciones asintóticas.
Otros miembros de la familia de notaciones asintóticas son las notaciones \(o\), \(\Omega\) y \(\theta\).
En geometría analítica, una asíntota es una linea que delimita el comportamiento de una función en su límite.
Esto es, la distancia entre la función y la linea delimitadora tienden a cero.
Al establecer que una función \(g\) es una asíntota de la función \(f\), estamos describiendo el comportamiento de \(f\) en el límite en términos de \(g\).
En la notación \(O\) nos interesa acotar el crecimiento de una función en términos de otra, por lo que:
Formalmente, \(O\) se define como:
Sean \(f\) y \(g\) dos funciones con dominio en los números reales positivos. Tenemos que \(f(n)=O(g(n)),\) o de forma alternativa \[f(n) \in O(g(n)),\] si y sólo si existen constantes \(N\) y \(C\) tales que, para toda \(n \geq N\), tenemos que\[|f(n)| \leq C |g(n)|.\]
Sea \(f(n) = n^3 + 20n + 1\), demostrar que \(f \in O(n^3).\)
Para que \(n^3 + 20n + 1 \leq C \cdot n^3\), necesitamos que \[C \geq \frac{n^3 + 20n + 1}{n^3}=1+\frac{20}{n^2} + \frac{1}{n^3}.\] Sigue que si \(n \geq 1\) y \(C \geq 22\) obtenemos la condición.
La siguiente definición es una condición equivalente a la anterior para \(O\):
Sean \(f\) y \(g\) dos funciones crecientes con dominio en los números reales positivos. Tenemos que \[f(n) \in O(g(n))\] si y sólo si
\[\limsup_{n\to\infty} \left| \frac{f(n)}{g(n)} \right| < \infty.\]
Supongamos que \[\limsup_{n\to\infty} \left| \frac{f(n)}{g(n)} \right| < \infty,\] por lo que existe \(C\) finito tal que \[\limsup_{n\to\infty} \left| \frac{f(n)}{g(n)} \right| < C,\] y para todo \(\epsilon > 0\) existe \(N\) tal que \(n\geq N\) implica \[\frac{|f(n)|}{|g(n)|} - C \leq \epsilon.\]
Sigue que \[|f(n)| \leq (C+\epsilon) \cdot |g(n)|,\] de donde obtenemos el resultado.
De forma análoga obtenemos la otra dirección. \(\Box\)
Sea \(f(n) = n^3 + 20n + 1\), demostrar que \(f \in O(n^3).\)
Ya que ambas funciones son monótonas crecientes distintas a 0, tenemos que \[\limsup_{n\to\infty} \left| \frac{ n^3 + 20n + 1}{n^3} \right|= \lim_{n\to\infty} \frac{ n^3 + 20n + 1}{n^3}\] y \[ \lim_{n\to\infty} \frac{ n^3 + 20n + 1}{n^3}= 1 + 0 + 0 < \infty.\text{ }\Box\]
Demostrar que \(\log_{b_1}n \in O(\log_{b_2}n)\) para toda \(b_1,b_2 > 1\).
Por la regla de L'Hôpital:
\[ \lim_{n\to\infty} \frac{\log_{b_1}n}{\log_{b_2}n}= \lim_{n\to\infty} \frac{n \log b_2 }{n \log b_1} = \frac{\log b_2 }{\log b_1} < \infty. \text{ } \Box \]
Notemos que: \[\begin{align} b_1^{\log_{b_1} n} &= n\\ \log_{b_2}(b_1^{\log_{b_1} n}) &= \log_{b_2} n\\ (\log_{b_1} n) \cdot \log_{b_{2}}(b_1) &= \log_{b_2} n\\ \end{align}\]
de donde para toda \(n > 0\): \[\log_{b_1}n \leq \frac{1}{\log_{b_{2}}(b_1)} \log_{b_2} n. \text{ } \Box\]
Regresemos a la expresión:
\[\limsup_{n\to\infty} \left| \frac{f(n)}{g(n)} \right| < \infty.\]
Notemos que:
Si ignoramos el factor constante entre ambas velocidades, tenemos que ambas crecen a la misma velocidad o, si el limite es 0, \(f\) crece más lento que \(g\).
De esta forma estamos acotando la velocidad del crecimiento de \(f\) en términos de \(g\).
Si \(f(n) \in O(g(n))\) decímos que \(f\) es del orden de \(g\).
Si \(f(n) \in O(g(n))\) pero \(g(n) \notin O(f(n))\) entonces decimos que \(g\) es de mayor orden (crece más rápido) que \(f\).
Si \(f(n) = O(g(n))\) y \(g(n) = O(f(n))\) entonces decimos que \(g\) y \(f\) tienen el mismo orden (crecen a la misma velocidad).
Si \(f(n)\) es el tiempo que toma un algoritmo en procesar una entrada de tamaño \(n\), entonces este orden jerárquico nos va a inducir una clasificación de los algoritmos en términos del su tiempo de ejecución.
Ya que no consideramos factores constantes, esta clasificación es robusta a distintas implementaciones y modelos de cómputo.
Sea \(c\) una constante mayor a 1.
| Notación | Nombre |
|---|---|
| \(O(1)\) | orden constante |
| \(O(\log \log n)\) | orden sublogarítmico |
| \(O(\log n)\) | orden logarítmico |
| \(O(\sqrt{n})\) | orden sublineal |
| \(O(n)\) | orden lineal o de primer orden |
| \(O(n \log^* n)\) | \(n\) log-estrella \(n\) |
| Notación | Nombre |
|---|---|
| \(O(n \log n)\) | orden lineal logarítmico o quasilineal |
| \(O(n^2)\) | orden cuadrático o de segundo orden |
| \(O(n^3)\) | orden cúbica o de tercer orden, etc. |
| \(O(n^c)\) | orden polinomial o algebraico |
| \(O(c^n)\) | orden exponencial |
| \(O(n!)\) | orden factorial |
Un parámetro primordial durante el desarrollo de proyectos de software es el poder controlar los recursos computacionales que un programa o sistema va ha utilizar durante su ejecución.
Para el análisis de algoritmos y la teoría de la complejidad computacional, los recursos más importantes son el tiempo y la memoria requeridas para la ejecución de un programa.
La notación \(O\) es usada para la clasificación de algoritmos ya que esta es robusta (depende poco) con respecto a diferencias de implementación así como del hardware disponible:
En general, el órdenes de complejidad de los recursos de ejecución se mantienen bajo diferencias en lenguaje de programación, habilidad del programador y diferencias de hardware.
La variable \(n\) representa el tamaño de la entrada tanto en bits, bytes, palabras o números de elementos de un problema de tamaño acotado, no importa cuál se use ya que, por la propiedad multiplicativa, el orden no va ha cambiar.
Para un algoritmo de ordenación como merge sort, \(n\) es el número de elementos a ordenar ya que, normalmente, estos van a ser de un tamaño fijo en bits.