ALGORITMO

Cuando solucionamos un problema mediante la construcción de un algoritmo, normalmente podemos atacar el problema desde distintos puntos de vista, aplicando distintas estrategias, y por tanto, llegando a soluciones algorítmicas distintas.

Desde el punto de vista computacional, es necesario disponer de alguna forma de comparar una solución algorítmica con otra, para conocer cómo se comportarán cuando las implementemos, especialmente al atacar problemas "grandes".

La complejidad algorítmica es una métrica teórica que se aplica a los algoritmos en este sentido. Es un concepto que fundamental para todos los programadores, pero sin embargo, a menudo se desconoce por completo. En muchos cursos y libros se elude el tema porque a menudo se considera farragoso.

Pero eso no es necesariamente cierto. La complejidad de un algoritmo es un concepto complicado pero sólo desde un punto de vista estrictamente formal. La obtención y el estudio de la complejidad de un algoritmo requiere ciertamente de unas cuantas destrezas matemáticas que no todos tenemos y la aplicación de una serie de técnicas bastante particulares. Sin embargo, no es un concepto difícil de entender.

Por hacer una similitud acerca de lo complicado que es este concepto, la dificultad de la complejidad es -salvando las distancias- como la de la predicción meteorológica: todos intuimos lo complicado que es hacer una predicción meteorológica, miles de datos, fórmulas, modelos y cálculos... sin embargo, cuando un meteorólogo nos explica con algo de gracia la predicción del tiempo, la podemos entender bastante bien. Ya estamos muy acostumbrados a cosas como borrasca, anticiclón, marejadilla, cota de nieve... Lo mismo pasa en cierto modo con la complejidad: enfrentarnos a un algoritmo para hacer un estudio de su complejidad requiere de un gran esfuerzo. Sin embargo, cuando alguien estudia un algoritmo y nos habla de su complejidad, entender el concepto no es tan complicado.

Entender la complejidad es importante porque a la hora de resolver muchos problemas, utilizamos algoritmos ya diseñados. Saber valorar su valor de complejidad puede ayudarnos mucho a conocer cómo se va a comportar el algoritmo e incluso a escoger uno u otro.

Así que en este artículo, nos vamos a dedicar a intentar exponer qué es la complejidad de un algoritmo desde un punto de vista sencillo y sin pretensiones, intentado distinguir qué impacto tiene el que un algoritmo tenga una u otra complejidad. Y, como de costumbre, adoptamos grandes simplificaciones, con el único ánimo de obtener una visión general de los conceptos. En cuanto a cómo obtener la complejidad de un algoritmo, no nos vamos a meter mucho: los formalismos necesarios quedan totalmente fuera del alcance de éste breve artículo divulgativo.