ASÍNTOTAS Y ÓRDENES DE COMPLEJIDAD

Ya tenemos una ligera idea informal de qué es la complejidad. Pero entonces ¿Cómo se comparan unos algoritmos con otros? Bueno... la idea de la complejidad de un algoritmo, es conocer cómo se comporta el tiempo de ejecución conforme la talla del problema va creciendo.... especialmente para valores muyyyy grandes... lo más grandes que podamos imaginar, y especialmente en el peor de los casos.

En ese contexto de tallas muy grandes podemos hacer otra "simplificación", por así decirlo. El hecho es que podemos encontrar ciertas similitudes entre las funciones que definen la complejidad de los algoritmos. Por ejemplo, si comparamos todos los algoritmos cuya complejidad es lineal (es decir, una recta... por ejemplo: 10n+3, 32n+12, 56n+1... o cualquier otro) y los comparamos con todos aquellos cuya complejidad es cuadrática (Por ejemplo, 2n²+3, 4n²+n, 6n²+4n+3...) y dibujamos sus funciones de complejidad en una gráfica observaremos que conforme n se va haciendo grande, tienen un patrón de crecimiento bien diferenciado.

En ese contexto, podemos agrupar todas las complejidades que crecen igual en el mismo saco. A ese saco le vamos a llamar órden de complejidad. Hablando un pelín más formalmente, para todas las funciones que agrupemos en un mismo orden, encontraremos una asíntota que al multiplicarla por un valor nos acote a nuestra función superiormente cuando estemos tratando el peor caso.

Por ejemplo, todas las complejidades cuadráticas están acotadas asintóticamente por "n²". Eso quiere decir que para cualquiera de las complejidades cuadráticas que hemos visto antes, por ejemplo 6n²+4n+3, existe un valor real c que hace que 6n²+4n+3 ≤ cn² cuando n se hace muy grande, es decir, cuando n→∞

De esta manera, la complejidad suele clasificarse en una serie de órdenes comunes.

La notación para expresar esto es como sigue: Por ejemplo, para decir que 6n²+4n+3 está determinado por la asíntota superior n², decimos "que 6n²+4n+3 pertenece al órden de n²" o "que 6n²+4n+3 es del órden de n²" y lo escribimos formalmente de ésta manera:

6n²+4n+3 ∈ O(n²)

Como ves, finalmente el concepto de complejidad se nos simplifica mucho. En lugar de hallar los tiempos exactos que tarda un algoritmo en solucionar los problemas, con lo que nos quedamos en con una asíntota que representa a todos los algoritmos cuyo tiempo crece de igual forma cuando la talla del problema tiende a infinito. Eso hace que el cálculo de la complejidad se simplifique mucho. Si no queremos hallar la función de complejidad real (y casi nunca queremos), sino el orden al que pertenece la complejidad del algoritmo, a la hora de hallarla, prácticamente ni siquiera tenemos que contar las instrucciones... Cada secuencia de instrucciones se cuenta como una sola instrucción. Lo que influye en la complejidad son principalmente los bucles y las sentencias de selección que tienen efecto sobre los bucles. En los algoritmos recursivos, la cosa se complica un poco más... Pero como hemos dicho al principio, el cálculo de la complejidad de un algoritmo queda fuera del alcance de éste artículo.

Cuando decimos que la complejidad de un algoritmo es de un orden concreto, por ejemplo n², podemos estar seguros de que para cualquier valor de n, y por muy mal que nos vayan las cosas (peor) caso, el valor que obtengamos nunca será mayor que cn², siendo c un real mayor que 1.