Comprendiendo la complejidad de algoritmos mediante ejemplos simples

Charles Babbage es considerado por muchos como el padre de la computación. De nacionalidad británica, vivió entre el 26 de diciembre de 1791 y el 18 de Octubre de 1871. Como matemático y científico de su época dependía de tablas de cálculo para sus trabajos. Tablas elaboradas por personas que por la naturaleza de esta tarea eran propensas al cansancio y el error.

Babbage molesto con los inconvenientes y retrasos causados por los errores de cálculo visualizó la creación de un ingenio mecánico que automatice su construcción. La máquina diferencial fue su respuesta a la necesidad de aproximar funciones logarítmicas y trigonométricas mediante polinomios. El 14 de Junio de 1822 la propuso a la Royal Astronomical Sociaty con el título "Nota sobre el uso de maquinaria para el cómputo de tablas matemáticas muy grandes".

Charles Babbage

Habiendo conseguido financiación del gobierno comenzó su fabricación. Pero pronto su genio lo empujó a encarar un proyecto más ambicioso: La máquina analítica. Dicho artilugio sería programable y podría resolver cualquier operación matemática. Utilizaría base decimal, tarjetas perforadas y se operaría mediante motor a vapor. Entre 1837 y el final de su vida Babbage trabajó en ella. Lamentablemente por carencias tecnológicas de la época y problemas de presupuesto nunca la pudo construir (más de 100 años después se tuvo que esperar para la construcción de una máquina funcional de características similares).

Babbage en su libro "Passages from the Life of a Philosopher" dedica el capítulo 8 "Of the analytical machine" a narrar diferentes situaciones alrededor de su intento de construcción. Entre ellos una charla en un desayuno con el Profesor MacCullagh de Dublin. Allí afirma:

"As soon as an Analytical Engine exists, it will necessarily guide the future course of the science. Whenever any result is sought by its aid, the question will then arise—By what course of calculation can these results be arrived at by the machine in the shortest time?"

Es decir, que la construcción de computadoras multipropósitos transformaría substancialmente el curso de la ciencia. La eficiencia en el calculo sería crucial. El estudio de como resolver un problema debía contener la minimización de los pasos necesarios para lograrlo. Diferentes algoritmos para un mismo problema se debían comparar para determinar cual es más eficiente. Incluso la comparación entre problemas y su complejidad (medido en mínimos pasos para realizarse) es posible. Sin saberlo y como al pasar profetizó una rama hoy de gran importancia y vitalidad: El análisis de los algoritmos y su complejidad.


Ada Lovelace, quien es considerada el primer programador en la historia (de quien hablamos en el artículo "Sobre el algoritmo, su origen y definición", en su análisis y notas de 1843 sobra la máquina analítica llego a la misma conclusión:

"In almost every computation a great variety of arrangements for the succession of the processes is possible, and various considerations must influence the selection amongst them for the purposes of a Calculating Engine. One essential object is to choose that arrangement which shall tend to reduce to a minimum the time necessary for completing the calculation"

El análisis de la complejidad algorítmica, tal su definición moderna se basa por lo tanto en el estudio de los recursos requeridos para algorítmicamente resolver cierto problema. Y como recursos se tienen en cuanta 2 dimensiones: el tiempo de ejecución y el espacio de almacenamiento requerido.

Conjunto de cartas de baraja española

Podemos usar un simple ejemplo para entender de que estamos hablando. Imaginemos que tenemos un conjunto de cartas de tipo español (digamos "n" cartas, siendo n la representación de un numero entero y positivo). Queremos determinar si una carta particular, el "7 de Oro", se encuentra dentro de ellas. Asumiremos que es posible que se haya perdido y es posible que hayan varios mazos mezclados.

La primera solución que podemos pensar es, simplemente, tomar el mazo y comenzando desde la carta superior pasar 1 a 1 a las cartas hasta encontrar la carta buscada. O terminar el proceso sin encontrarla si no estaba. Algorítmicamente:

1. Iniciar en la carta numero 1.
2. Si la carga es la buscada, informar que la encontramos
3. Si no, si quedan más cartas, pasar a la siguiente y repetir desde el paso 2.

Si consideramos que una operación es pasar a la siguiente carta, en el peor de los casos debemos realizarlo "n" veces. También podemos, con suerte encontrarla a la primera. Por último también se podría realizar un estudio estadístico y determinar cuál sería la cantidad promedio de operaciones necesarias para encontrarla.

Estos tres indicadores son utilizados dentro del análisis de algoritmos. Se los conoce respectivamente como peor caso, mejor caso y caso promedio. Por regla general el peor caso es el que suele utilizarse para comparar entre algoritmos. Esta elección podría ser objetada. Por qué utilizar un caso muy malo entre millones mejores? La respuesta es práctica: instalaría un programa por ejemplo para controlar un automóvil autónomo que en promedio funcionó muy bien, pero que tiene ciertos casos (o al menos 1 caso) que bajo ciertas circunstancias no llega a reaccionar a tiempo y puede ocasionar una colisión?

Y que pasa con el espacio de almacenamiento necesario? En nuestro algoritmo tenemos que tener espacio para procesar el mazo de cartas (tamaño de entrada) y tenemos el espacio adicional para el procesamiento en si mismo. En el análisis de algoritmos se tiene en cuenta ese tamaño adicional en relación al tamaño de la entrada. Si consideramos que en nuestro algoritmo retornamos si la carta está o no y no guardamos nada adicional entonces el tamaño de almacenamiento es constante independiente de la cantidad de cartas o tamaño de la entrada.

Por lo tanto podemos clasificar a nuestro algoritmo como lineal en relación al tiempo de procesamiento (si tengo el doble de cartas necesitaré el doble de tiempo).  Y constante en cuestión de espació extra (aún si tengo un millón de cartas más, el indicador de encontrado seguirá siendo solo 1).

El objetivo de quienes diseñan algoritmos para resolver problemas es hacerlo de la forma más eficiente. Es decir minimizar los recursos necesarios. Es nuestra solución la más eficiente? Podemos evitar mirar todas las cartas?

Una idea que surge naturalmente es, ¿qué pasaría si las cartas están ordenadas? Mirando nuestro algoritmo, lo puedo mejorar un poco. Imaginemos que dentro del ciclo de búsqueda del 7 de oro encuentro el 8 de oro. Cómo las cartas están ordenadas (de menor a mayor) ya no tengo que seguir revisando. La carta que busco no está.  Lamentablemente si bien puedo tener una mejoría en caso promedio, el peor caso se mantiene: Busco la carta más grande y la misma no se encuentra.

Existe una solución mejor, se la conoce como búsqueda binaria. El algoritmo se lo podría escribir de la siguiente forma:

1. Tomo el mazo y lo separó en dos pilones iguales.
2 si la carta que queda en el medio es la que busco, informar que la encontramos.
3. Si la carta es mayor a la buscada descartar todas las cartas del segundo pilón (que contiene todas cartas mayores a la buscada)
4. Si la carta es menor a la buscada descartar el primer pilón.
5. repetir el proceso hasta encontrar la carta o que no se pueda seguir dividiendo el mazo

Qué está haciendo el algoritmo? En cada paso eliminó la mitad de las cartas que quedan. Si tengo n cartas, en una primera pasada tendré n/2, luego n/4, n/8...  Hasta finalizar. Luego de logaritmo en base 2 de n iteraciones como máximo terminaré.

La búsqueda binaria tiene una complejidad temporal logarítmica. Está es menor a la lineal (como se muestra en la tabla siguiente). Como ejemplo si tengo que buscar una carta entre mil, en el peor de los casos tendré que realizar 10 operaciones de división de a mitades con nuestra búsqueda binaria. 

Tabla comparativa de cantidad de operaciones
según cantidad de elementos a procesar

Tenemos un algoritmo para el problema de buscar un elemento dentro de un conjunto que es más eficiente a nuestro algoritmo original. Con la salvedad (no menor) de que solo nos sirve si nuestras cartas están previamente ordenadas. Este es un subproblema dentro del problema original. No podemos pretender que las cartas estén previamente ordenadas.

Es esperable que alguien proponga ordenar el mazo de naipes antes de buscar la carta. De esa manera, razonan, la búsqueda es más eficiente. Muchos programadores novatos (y otros no tanto) se apresuran a tomar esta solución. Se olvidan que para calcular la complejidad de un problema, si el mismo se divide en varios procesos, se calcula como la suma de la complejidad de sus partes.

Cuál es la complejidad de ordenar elementos? Existen muchos algoritmos que resuelven este predicamento. Comencemos por uno sencillo. El mismo es conocido como "selection sort". Este algoritmo se puede resumir como:

1. Comenzar con todas las cartas en una pila y otra pila vacía
2. Desde la primer a la ultima carta buscar la menor y pasarla a la parte superior de la otra pila
3. Repetir el procedimiento hasta que todas las cartas estén en la otra pila.

En este caso la complejidad temporal se puede ver como la cantidad de veces que se tienen que observar las cartas. Si tengo n cartas, la primera vez busco el menor entre todas ellas. La segunda vez se tiene que buscar entre n-1, y así "n" veces en total. En total se observan (n*n + n) / 2 veces las cartas. Cuando la cantidad de cartas es muy grande, el factor preponderante en la fórmula es n*n, por lo tanto en el análisis de su complejidad se simplifica la expresión y se dice que su complejidad tiene un crecimiento de tipo cuadrático (n al cuadrado o "n por n").

Visualización de complejidad
en función de cantidad n de elementos

Usando selection sort y luego búsqueda binaria nos quedaría una complejidad de n2 + log n que es mayor a simplemente buscar linealmente (en la tabla seria sumar la columna 2 y la 4. Luego compararla con la columna 1). Pero, no existe un método para ordenar más eficiente?

Existen gran cantidad de algoritmos de propósito general para ordenamiento: insertion sort, buble sort, merge sort, quick sort, heap sort, Tim sort... entre otros. El análisis de complejidad de los mismos nos enseña que en el mejor caso como mínimo tengo que observar una vez todas las cartas (para saber por ejemplo si ya se encuentran previamente ordenados) y en el peor de los casos tiene una complejidad de n * log n. Tim Sort es un algoritmo creado en 2002 para el lenguaje Python que cumple las cotas antes nombradas (También es uilizado en las últimas versiones de Java).

La pregunta que puede surgir es, no será que aun no se inventó un algoritmo mejor? Pero, la respuesta es negativa. Está demostrado que la cota inferior (del peor caso posible) siempre será n log n.

Alguien astuto podría observar: aunque tenga 100 millones de cartas de baraja española en el peor de los casos solo hay 48 cartas diferentes. Por lo tanto puedo ir recorriendo cada carta y apilándolas en 48 montones diferentes. Luego simplemente apilo en orden esos pilones. Esos son "n" operaciones de apilado +  48 de apilado de pilones. Si la cantidad de cartas es muy grande se puede ver como un proceso de magnitud lineal.  Que es menor a la "supuesta" cota inferior de los métodos de ordenamiento. Pero, de nuevo, hablamos de métodos de ordenamiento generales que funcionen bien con cualquier conjunto de elementos a ordenar. En este caso suponemos que tenemos muchos elementos repetidos (corresponde a un subproblema del problema de ordenamiento). Y aun así, estoy recorriendo todos las cartas para ordenarlas y luego realizando la búsqueda (hacemos un doble trabajo cuanto mínimo).

Por lo tanto, ordenar para buscar un elemento determinado es una muy mala idea. El análisis de la complejidad nos enseña eso. Tampoco es buena idea ordenar para obtener solo el elemento más grande (o el más pequeño) de conjunto de elementos.

El ejercicio que realizamos sobre un caso sencillo se aplica a todos los ámbitos de la algoritmia. Para un problema determinado podemos idear diferentes formas de solucionarlo.  Comparar entre esas soluciones nos ayuda a tomar decisiones inteligentes de cual utilizar y en que caso. Incluso el descubrimiento de nuevas soluciones las podemos analizar a la luz de las existentes.