Introducción: análisis de algoritmos II

Antes de leer este post, puedes necesitar leer la introducción I aqui.

Notación asintótica

La notación asintótica, es una notación matemática formal que nos permite expresar las cotas bajo las que se encuentra el costo de cierto algoritmo, donde el costo puede ser en tiempo de ejecución, espacio requerido de almacenamiento, entre otros. Básicamente podemos acotar un algoritmo superiormente (O), inferiormente (Ω), y exactamente (Θ).

En el orden de (O)

Para explicar este concepto, imaginemos que tenemos una función cualquiera: t(n)=n²+2n+3. Supongamos que n es el tamaño de un ejemplar sobre el que queremos aplicar un algoritmo, y t(n) es la cantidad de  algún recurso que consume el algoritmo (tiempo, espacio…).

Antes de continuar, es necesario introducir el concepto del principio de invarianza, que dice que la razón de los tiempos de ejecución de dos implementaciones diferentes de un mismo algoritmo, siempre está acotada por encima y por debajo por constantes predeterminadas, donde las constantes pueden depender de las implementaciones de un algoritmo, pero no del tamaño del ejemplar en el que usaremos el algoritmo.

Ahora contemplemos otra función f(n)=n². Podremos decir que t(n) está en el orden de f(n), si t(n) está acotada superiormente por un múltiplo real positivo de f(n) para todo n suficientemente grande.  Dicho matemáticamente, significa que existe una constante real y positiva c y un umbral entero n₀ tal que:

t(n) ≤ c f(n), siempre que n ≥ n_{0        (0)}

Ahora para entender esto, tomaremos las funciones definidas anteriormente, t(n)=n²+2n+3 y f(n)=n². En t(n) aparece una n², una n y una constante (3), ¿cuál de estas expresiones en más grande?.  Está claro que n≤n² y que 1≤n², siempre y cuando la n≥1 (si n=0, esto no se cumple), entonces, tomaremos el término más grande que es n² y lo sustituimos en los demás términos más pequeños que son n y 1 ( 1 porque el último término de la función es 3, pero ocultamente ese 3 al ser una constante, está multiplicando al 1). Entonces tenemos que para n≥1:

t(n)=n²+2n+3          (1)

≤ n²+2n²+3n^{2           (2)}

≤ 6n^{2                         (3)}

≤ 6 f(n)                       ⁽⁴⁾

En la Ec.(2) sustituimos el término más grande, entonces obviamente, el valor original de t(n), se vuelve menor que la nueva expresión. En la Ec.3 solo sumamos los términos y en Ec. 4, sustituimos n²por f(n), que vale lo mismo. Entonces podemos observar que la constante de la que hablamos en la Ec.0, en éste ejemplo es c=6, y  n₀=1. Dado que si existe una constante real positiva c, en un umbral entero , entonces podemos decir, que t(n), está en el orden de f(n).

Ahora, ya hemos dicho que t(n) puede representar cualquier unidad de costo, ya sean microsegundos, bits, años, etc. esto dependiendo de lo que estemos midiendo en nuestro algoritmo (después veremos la forma de obtener t(n)), pero por poner un ejemplo, diremos que nuestro algoritmo ejemplo tarda n²+2n+3 microsegundos en resolver un ejemplar de tamaño n, y ahora podemos decir que éste tiempo, está en orden de n² . Ahora bien, es válido decir que t(n) está en orden de f(n) para cualquier implementación de nuestro algoritmo, dado el principio de invarianza.

Para denotar matemáticamente “en el orden de”, se utiliza el simbolo “big O”, también conocida como “O grandota”. Por lo que es correcto expresar: t(n) O(f(n)), en nuestro ejemplo: (n²+2n+3) ϵ O(n²)