Hace unos años presencié una discusión entre dos programadores sobre la “eficiencia de los programas“. Ellos discutían sobre la manera de especificar el problema en la herramienta CASE que utilizaban, para que el programa generado fuera más “eficiente“. La discusión era acalorada y tenían visiones muy diferentes del asunto (yo, al no conocer ni de cerca la herramienta en cuestión, no entendía ni media palabra de sus argumentos).

Hasta que en un momento no pude contenerme y decidí meter el dedo en el ventilador: A ver, una pregunta, ¿cuándo un programa es más eficiente que otro? – les dije. Para mi asombro (aunque debería haberlo intuído), ambos me respondieron al unísono: ¡Cuando es mas corto!.

No soñaría por un instante que la mayoría de los programadores viven en tal ignorancia, pero sin embargo muchos no tienen demasiada claridad acerca de este asunto. Más aún, ni siquiera son conscientes de la enorme diferencia que puede haber, a la hora de la ejecución, entre dos programas equivalentes pero de diferente complejidad temporal. Pensando en esto, recordé un ejemplo utilizado por dos de mis mejores profes en un artículo llamado “La perplejidad como recurso didáctico“.

Este ejemplo muestra cómo un cambio aparentemente sutil en un algoritmo puede impactar tremendamente en el rendimiento del programa resultante.

El problema

Supongamos que tenemos que escribir un programa para calcular potencias naturales de 2. Para ello podemos usar las operaciones aritméticas de suma y producto.

Una solución posible sería calcular:

• 2⁰ = 1
• 2ⁿ = 2 * 2^{n – 1}, para n > 0

Una alternativa sería considerar el caso “n > 0″ de forma diferente: sumando dos veces 2^{n – 1} en vez de multiplicando por 2. Esto es:

• 2⁰ = 1
• 2ⁿ = 2^{n – 1} + 2^{n – 1}, para n > 0

Puede verse claramente que ambas soluciones son matemáticamente equivalentes.

A continuación, el código en lenguaje pascal de las dos soluciones (pow1 y pow2, respectivamente). Por simplicidad se ha declarado el exponente a calcular como una constante igual a 10:

pow1.pas


program pow1;
const exp = 10;
function pow(n: integer): integer;
begin
    if n = 0 then
        pow := 1
    else
    pow := 2 * pow(n-1);
end;
begin
    writeln(pow(exp));
end.


pow2.pas


program pow2;
const exp = 10;
function pow(n: integer): integer;
begin
    if n = 0 then
        pow := 1
    else
    pow := pow(n-1) + pow(n-1);
end;
begin
    writeln(pow(exp));
end.


Complejidad temporal

Sin entrar en demasiados detalles técnicos (ver los enlaces al final del artículo), analizaremos la eficiencia de cada uno de estos programas.

Primero vamos a suponer que el costo en tiempo de realizar las llamadas recursivas es despreciable y que el costo de realizar una suma o una multiplicación es una unidad de tiempo (luego veremos que esto no afecta el resultado que nos interesa destacar).

En el caso de pow1 vemos que la primera llamada a pow se hace asignando a n el valor inicial exp, y luego en cada llamada recursiva este valor se decrementa en 1. Esto significa que para calcular 2ⁿ se harán n llamadas recursivas (multiplicando en cada caso el valor resultante por 2), lo cual insumirá n unidades de tiempo.

En el caso de pow2 la situación es diferente: en cada llamada a pow se hacen dos nuevas llamadas recursivas, para luego sumar los resultados. Esto significa que para calcular 2ⁿ se harán 2ⁿ llamadas recursivas (sumando en cada caso los valores resultantes), lo cual insumirá 2ⁿ unidades de tiempo.

De este análisis se desprende que pow1 requiere de un tiempo del orden de n (lineal), en tanto que pow2 requiere de un tiempo del orden de 2ⁿ (exponencial).

¿Y todo esto qué significa?

En términos prácticos todo esto significa, ni más ni menos, que pow1 es un programa que resuelve el problema de forma razonable (aunque podría ser mucho más eficiente), en tanto que pow2 es (al menos si pensamos en valores grandes de n) una porquería.

Supongamos que tenemos una computadora capaz de ejecutar 1.000 operaciones por segundo. La siguiente tabla muestra aproximadamente cuánto tardaría la ejecución de cada uno de nuestros programas para distintos valores de n.

Si bien 1.000 operaciones por segundo no parece una velocidad razonable para una computadora de estos tiempos, podríamos multiplicarla por varios millones y aún no podríamos calcular 2¹⁰⁰ usando el programa pow2.

Lo más notable es que no importa si la computadora que utilicemos es “2 veces”, “10 veces” o “100 veces” más rápida: el salto en las diferencias de tiempo, pasado determinado valor de n se mantendrá de todas formas.

Amén de que se trata de un ejemplo arbitrario (pero contundente), vale para mostrar la gran importancia que puede tener sobre la eficiencia de un programa una pequeña modificación sobre el algoritmo utilizado. Lamentablemente no es poco común ver programas que se ejecutan razonablemente bien con una pequeña cantidad de datos, pero cuyo funcionamiento se vuelve intolerable cuando estos crecen.

Cada vez que pienso en esto, me pregunto qué será de aquellos dos programadores y los usuarios de sus sistemas…

Lecturas adicionales

A continuación, algunos enlaces con información sobre complejidad computacional:

• Wikipedia en inglés
• Wikipedia en castellano
• Complexity Zoo