El acceso a los ordenadores ha permitido a los científicos explorar problemas que antes estaban fuera de nuestro alcance. Ese avance en la computación podemos dividir en dos partes:

1.- Construir 'hardware' cada vez más potente.

2.- Inventar nuevos algoritmos para resolver en mucho menos tiempo el mismo problema usando el mismo hardware.

Evidentemente para fabricar hardware también se necesitan ideas, pero para en este post lo que discutiremos es cómo ha sido la velocidad del avance de los algoritmos.

1.- ¿Qué es un algoritmo?

Un algoritmo es una serie de instrucciones para resolver un problema nada más.

Por ejemplo: el algoritmo para preparar mi desayuno es algo así:

1.- Mete pan en la tostadora.

2.- Espera a que esté tostado y sácalo.

3.- Echa colacao en una taza.

4.- Vierte leche sobre el colacao.

Esta serie de instrucciones constituye un algoritmo para resolver el problema llamado hacerme el desayuno.

Para un mismo problema, podemos crear algoritmos que lo resuelven más rápido. Ejemplo:

1.- Mete pan en la tostadora.

2.- Mientras el pan se está calentado, echa colacao en una taza.

3.- Vierte leche sobre el colacao.

4.- Saca el pan de la tostadora.

Este es otro algoritmo válido y mucho más rápido: en el primer algoritmo yo estaba parado mientras se tostaba el pan. Aquí aprovecho ese tiempo para prepararme el colacao.

De la misma manera han avanzado los algoritmos para los problemas más serios como nos explican en un fascinante estudio Yash Cherry y Neil Thompson, dos científicos del MIT, que han rastreado minuciosamente 57 libros de texto de Teoría de la Computación y más de 1.000 artículos.

¿En qué época se inventaron más algoritmos?

Cherry y Thompson comienzan dividiendo todos los algoritmos deterministas conocidos en 113 familias.

Como podéis ver en la siguiente figura, la mayoría de esas familias de algoritmos se inventaron en los años 1940 o antes. Genios como Alan Turing o Von Neumann ya los tenían en la cabeza antes de tener una máquina en la que programarlos.

¿En qué época se mejoraron más los algoritmos?

Los investigadores explorar después las décadas en las que se consiguió que alguna familia de algoritmos bajase de su clase de complejidad.

Los años 70 del pasado siglo fue la época dorada:

¿Cómo se mide si un algoritmo 'mejora'?

Los teóricos de la computación utilizan algo que se llama 'clases de complejidad asintótica'. Por ejemplo: si un algoritmo que está en la clase n2 significa que el tiempo que consume ese algoritmo para encontrar la solución crece de manera cuadrática con el tamaño del input.

Las principales 'clases' de algoritmos (de más lento a más rápido) son: n factorial, n al cubo, n al cuadro, n log n, n, log n y por último la clase 1.

Los investigadores también han calculado cuál ha sido la probabilidad anual de que un algoritmo bajase de clase de complejidad:

¡La ley de Moore no sólo se aplica al hardware, también a las ideas!