Notación O Grande
Hoy veremos una forma de analizar nuestros algoritmos en cualquier lenguaje de programación:
Notación O Grande:
Comencemos con una definición
Definición:
Sea \(g(x)\) una función de variable real definida para todo real no negativo. Denotamos por \(O(g(x))\), leído como O grande de \(g\), el conjunto
\[\begin{aligned} O(g(x))& =\{f(n): \text{ existen reales} c>0 \text{ y } b \geq 0 \text{ tales que}\\ & \quad |f(x)| \leq c|g(x)|, \text { para todo } x \geq b\} \end{aligned}\]Pero, ¿y esto de qué nos sirve?
Básicamente podemos analizar nuestros algoritmos y contar las operaciones que hacen en cada una de las iteraciones, de esta forma obtener una función \(g(x)\) y con \(O(g(x))\) podemos ver el crecimiento de la misma comparado con otras funciones
¿Y esto qué nos dice de nuestro algoritmo?
Nos dice que qué tanto le tomará darnos un resultado dependiendo del tamaño de la tarea que le asignemos
No es lo mismo para un computador multiplicar 2 números de 100 dígitos que dos de 4 millones de dígitos, entonces la velocidad en la que nos entregue el resultado depende enteramente de nuestra capacidad de desarrollar algoritmos eficientes.
En la publicación de “División por tentativa” vimos como al implementar un pequeño teorema en teoría de números ahorramos mucho tiempo en factorizar un número por ejemplo.
Ejemplo:
Si \(f(n)=n^2+10^{10} n\), entonces \(f=O\left(n^2\right)\). En efecto,
\[\begin{aligned} & |f(n)|=\left|n^2+10^{10} n\right| \\ & \leq n^2+10^{10} n \quad(n \geq 0) \\ & \leq n^2+10^{10} n^2 \quad(n \geq 1) \\ & =\left(10^{10}+1\right) n^2=c\left|n^2\right| \text {, } \\ \end{aligned}\]con \(c=10^{10}+1\)
Require: \(n \in \mathbb{Z}\)
\[\text{1: procedure ALGEJER2}\] \[\begin{array}{lc}2: & \text { for } i:=1 \text { to } n \text { do } \\ 3: & \text { for } j:=1 \text { to } i \text { do } \\ 4: & \text { for } k:=1 \text { to } j \text { do } \\ 5: & x:=i \cdot j \cdot k \\ 6: & \text { end for } \\ 7: & \text { end for } \\ 8: & \text { end for } \\ 9: & \text { end procedure } \end{array}\]Este algoritmo por ejemplo hace dos multiplicaciones para calcular el producto de 3 enteros y tiene 3 for anidados.
Notemos que el primer for va acumulando las operaciones que se hacen en los 2 de adentro, el último for ejecuta las 2 operaciones, luego para el segundo sumamos estas operaciones que se van acumulando y obtenemos:
\[\sum_{m=1}^i 2 m=i(i+1)\]Como dijimos el primer for suma estas operaciones luego el total de operaciones que hace el algoritmo es:
\[\sum_{i=1}^n i(i+1)=\frac{n(n+1)(n+2)}{2}\]al multiplicar los términos nos damos cuenta que el algoritmo es \(O\left(n^3\right)\) (o de orden cúbico)
Note que esto es un abuso de notación tremendo, pero lo importante es que sirve $x d$, ahora veamos el tiempo computacional.
Asumiendo que una operación toma un nanosegundo ( \(10^{-9}\) segundo), comparamos el tiempo computacional para diferentes ordenes de una función \(f(n)\) a continuación.
\[\tiny{\begin{array}{|c||c|c|c|c|} \hline f(n) & n=10 & n=10^3 & n=10^5 & n=10^7 \\ \hline \log _2(n) & 3,3 * 10^{-9} \mathrm{~s} & 10^{-8} \mathrm{~s} & 1,7 * 10^{-8} \mathrm{~s} & 2,3 * 10^{-8} \mathrm{~s} \\ n & 10^{-8} \mathrm{~s} & 10^{-6} \mathrm{~s} & 0,0001 \mathrm{~s} & 0,01 \mathrm{~s} \\ n \log _2(n) & 3,3 * 10^{-8} \mathrm{~s} & 0,000010 \mathrm{~s} & 0,0017 \mathrm{~s} & 0,23 \mathrm{~s} \\ n^2 & 10^{-7} \mathrm{~s} & 0,0010 \mathrm{~s} & 10 \mathrm{~s} & 27 \text { horas } \\ n^3 & 10^{-6} \mathrm{~s} & 1 \mathrm{~s} & 11,5 \text { días } & 31709 \text { años } \\ 2^n & 10^{-6} \mathrm{~s} & - & - & - \\ \hline \end{array}}\]Luego el orden logaritmico sería lo más ideal si queremos que nuestros programas compilen rápido y el exponencial el peor, para tareas pesadas nos podemos morir sin conocer el resultado.