LA COMPLEJIDAD NO ES UN NÚMERO. ES UNA FUNCIÓN.

Otra consideración a tener en cuenta a la hora de tratar con la complejidad es que si estamos contando el tiempo que tarda un algoritmo en resolver un problema ¿En qué ordenador lo ejecutamos? Parece obvio que el mismo algoritmo ejecutado en un ordenador el doble de rápido que otro tardará la mitad en encontrar la solución. ¿Cuál debería ser entonces la unidad de medida de la complejidad? Ninguna unidad de tiempo nos vale: ni segundos ni milisegundos, porque el resultado variaría de un ordenador a otro.

Además... parece obvio también que el mismo algoritmo tardará más o menos en solucionar un problema de una talla u otra. Es decir, no puede tardarse lo mismo en ordenar un array de 100 valores que uno de 100000.

Bueno... pues vamos a adoptar una simplificación que nos permita no tener en cuenta en qué ordenador se ejecutará el algoritmo: en lugar de medir tiempos, vamos a contar las instrucciones que debe realizar el algoritmo. Supondremos que cada instrucción se ejecuta en un tiempo constante.

Nos podemos permitir esa simplificación porque lo que realmente queremos saber es cómo crece el número de instrucciones necesarias para resolver el problema con respecto a la talla del problema. Eso es realmente la complejidad.

Por ejemplo, observa ésta función (da igual cuál sea su propósito).

01 funcion ejemplo(n: entero):entero
02 empieza
03    variables: a, j, k enteros
04    para j desde 1 hasta n hacer
05        a=a+j
06    fin para
07    para k desde n hasta 1 hacer
08        a=a-1
09        a=a*2
10    fin para
11   devolver a
12 termina

En este algorimo hay un par de bucles para que se ejecutan uno después del otro.

Observemos el primer bucle. Se ejecuta n veces, y en su interior hay una instrucción (la de la línea 5). Eso quiere decir que la línea 5 se ejecuta n veces. Después se ejecuta el segundo bucle, que contiene en su interior dos instrucciones (las de las líneas 8 y 9). Como ese segundo bucle se ejecuta también n veces y tiene dos instrucciones, se realizan 2n instrucciones. Finalmente hay una instrucción en la línea 11 que se ejecuta una sola vez.

Bien.... el número de instrucciones que se ejecutan en total son n+2n+1... es decir, 3n+1

Todavía no hemos llegado al fondo de la cuestión, pero vamos encaminados. Podemos decir que la complejidad de ese algoritmo es 3n+1, porque ese es el número de instrucciones que hay que realizar para solucionar el problema cuando la talla del problema es n.

La idea que subyace es que podemos saber cómo se comporta el algoritmo conforme la talla del problema va creciendo. En este caso, si representamos 3n+1 con respecto a n nos daremos cuenta de que esta función es una recta. Para este algoritmo podemos suponer que cuando lo traslademos a un lenguaje de programación concreto sobre un ordenador concreto, si para un n=100 tarda 7 unidades de tiempo en solucionarlo, con unas pocas operaciones podemos deducir cuántas unidades de tiempo tarda para un n=1000. Por supuesto, no es un valor exacto, pero lo que nos importa es saber de qué manera aumenta el tiempo con respecto a la talla del problema.

Para terminar de ver la importancia de esto, vamos a ver un par de funciones más de ejemplo.

01 funcion ejemplo2(n: entero):entero
02 empieza
03    variables: a entero
04    a=n*3
05    a=a+2
06    devolver a 
07 termina
 
01 funcion ejemplo3(n:entero): entero
02 empieza
03     variables i, j, k enteros
04     para i=1 hasta n hacer   
05        para j=n hasta 1 hacer
06           k=k+j
07           k=k+i
08        fin para
09     fin para
10     devolver k
11 termina

La funcion ejemplo2 realiza siempre 3 instrucciones (las líneas 4, 5 y 6), independientemente de lo que se le pase como parámetro. Así pues, este algoritmo siempre tarda lo mismo para cualquier valor de n. El número de instrucciones se mantiene constante, a diferencia del ejemplo anterior, que crecía linealmente con respecto a n.

La función ejemplo3 tiene dos bucles para anidados. Cada bucle se ejecuta n veces, y en el interior del segundo hay 2 instrucciones. Ej bucle interior hace que las dos instrucciones se repitan n veces, y el bucle exterior hace que todo eso se repita n veces más. Después hay una última instrucción (la de la línea 10). Así pues, se hacen 2×n×n+1 instrucciones... es decir, 2n²+1.

Si representamos 2n²+1 con respecto a n en un gráfico nos podemos dar cuenta de que es una parábola... es decir, el tiempo crece muchísimo más rápido conforme crece n que en los ejemplos anteriores. En este caso, el tiempo crece cuadráticamente. Igual que ocurría en los ejemplos anteriores, si en una determinada máquina para n=100 se tardan 7 unidades de tiempo, con unas pocas operaciones podemos intuir cuánto va a tardar para un n=1000 o para cualquier otro valor.

Lo importante de la idea expuesta hasta ahora es que los distintos algoritmos se comportan de forma distinta. Su tiempo de ejecución varía de manera muy distinta conforme aumenta la talla del problema.

Quizá éste gráfico resulte más clarificador.

El eje horizontal representa a la talla del problema (n), y el eje vertical al número de instrucciones necesarias de nuestros tres ejemplos.

La línea verde corresponde al primer ejemplo. Su número de instrucciones, y por tanto su tiempo de ejecución crece linealmente conforme n se hace más grande.

La línea azul corresponde al segundo. El número de instrucciones necesarias se mantiene constante, por muy grande que sea n.

La línea granate corresponde al tercer ejemplo. El número de instrucciones crece proporcionalmente al cuadrado de n conforme crece n.

Independientemente de los valores numéricos, resulta evidente que cada gráfica crece de manera distinta. A medida que n se vaya haciendo grande, las tres gráficas se distanciarán cada vez más.

Eso es lo que nos importa realmente de un algoritmo: saber cómo crece el número de instrucciones a realizar conforme lo apliquemos cada vez a problemas más grandes, más que el tiempo medido en segundos.