La importancia de un buen algoritmo

Hacía tiempo que no dedicábamos una entrada específica relacionada con el mundo de la programación. Hoy vamos a hablar sobre los algoritmos, las distintas maneras de crearlos y los comportamientos de unos frente a otros.

Podríamos resumir el término algoritmia, como la ciencia que estudia los algoritmos, tanto su creación como su análisis. Para conseguir mejoras y seleccionar el más efectivo para cada tarea.

La algoritmia : la base de un buen programa

Muchos usuarios cuando empezamos a programar, utilizamos la típica frase de “lo importante es que funcione”, claro que es importante que el programa funcione. Pero si hay cuatro programas que cumplen con el objetivo, seguramente los cuatro no afronten el problema de la misma manera.

Para resolver un problema, se pueden utilizar múltiples métodos y algoritmos ya creados, aunque normalmente estos los tenemos que utilizar como base para crear nuestro algoritmo. El algoritmo debe ser refinado tanto como sea posible para agilizar el tiempo que tarde en ejecutarse nuestro programa.

Por ejemplo, si partimos de un programa que gestione facturas con unas 1000 líneas de código, no hay que buscar la optimización línea por línea, sino mirar que parte es la que tarda más tiempo, por ejemplo la ordenación y afrontar esta parte del programa, buscando mejorar su algoritmo. Hay algunos algoritmos que son difícilmente mejorables y otros que simplemente no se pueden mejorar, pero la mayoría de ellos suelen tener mejoras muy interesantes.

La creación de un algoritmo : un sencillo problema

Supongamos el problema: quiero que me hagas una lista de los números múltiplos de 4 y de 5 al mismo tiempo que hay en el rango 1-1.000.000

Lo primero que piensa un usuario, principalmente si es novato es utilizar el típico método de fuerza bruta:

#include <stdio.h>
#include <stdlib.h>
 
int main(){
int i;
int flag=0;
    for(i=1;i<1000001;i++){
        if(i%4==0){
            flag=1;
        }
        if(i%5==0 && flag==1){
            printf("%d\n",i);
        }
    }

return 0;
}

Este es el típico ejemplo de “pero si ya funciona, para que lo voy a mejorar”. Lo importante es que este sistema hace 3.000.000 comparaciones, por cada número compara si es múltiplo de 4 y si es de 5 y si cumple las dos condiciones, lo muestra.

Refinando el algoritmo

Seguro que alguno de nuestros lectores ha encontrado una sencilla manera de mejorar el código:

#include <stdio.h>
#include <stdlib.h>

int main(){
    int i;
    for(i=1;i<1000001;i++){
        if(i%4==0 && i%5==0){           
            printf("%d\n",i);           
        }
    }
return 0;

}

Este sencillo arreglo evita un gran número de comparaciones, porque si el número no es múltiplo de 4 para que vamos a calcular si es múltiplo de 5, si ya no cumple la propiedad que nos pide el problema.

Repensando el algoritmo

Muchas veces nos quedamos atascados pensando que nuestra manera, es la mejor forma de afrontarlo. Pero después de unas horas desconectados del problema, se nos ocurre lo siguiente:

#include <stdio.h>
#include <stdlib.h>

int main(){
    int i=5;
    while(i<1000001)
        if(i%4==0){         
            printf("%d\n",i);           
        }
        i+=5;
    }
return 0;

}

Esta última solución es bastante mejor, que lo planteado, ya no vamos probando todos los números, sino que generamos una lista de múltiplos de 5 y de esos múltiplos miramos cuales son también múltiplos de 4.

Resumiendo

Midiendo el tiempo, con un cronómetro, he conseguido darme cuenta que entre la solución primera y la tercera hay una mejora (en mi máquina de dos segundos). Esto podría parecer poco, pero si pensamos en que el rango que nos pidan sea entre 1 y un trillón, lo mismo la mejora no se mide en segundos, sino en minutos. Por eso y con este ejemplo, he intentado aclararlo, es muy importante mejorar nuestros algoritmos.