Complejidad Algorítmica

La teoría de la complejidad algorítmica tiene como objetivo clasificar cualquier problema que se pueda computar atendiendo al esfuerzo computacional requerido para su resolución. Para medir dicha complejidad, no se tienen en cuenta destalles de bajo nivel acerca de las características hardware de la máquina, y nos centramos en los detalles del algoritmo en sí, de manera que nos fijaremos en la frecuencia de ejecución de las instrucciones del algoritmo.

(1) a = 1;

(2) desde i=1 hasta n hacer

a = a+i;

(3) desde j=1 hasta n hacer

desde k=1 hasta n hacer

a = a+j+k

En este caso la complejidad para cada segmente de código es O(1) para el segmente (1), O(n) para el segmente (2) y O(n²) para el segmente (3). Así denotamos la complejidad de un algoritmo con la expresión O(g(n)).

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O (n³) < O(2ⁿ)

En estos momentos disponemos de una medida estándar que nos permitirá expresar la eficiencia computacional de un algoritmo, y comparar diferentes soluciones a un mismo problema. Por ejemplo el algoritmo de ordenación QuickSort, tiene una complejidad del orden de O(n log n) [1] siendo n el tamaño del vector a ordenar, y el algoritmo de la burbuja del orden de O(n²) [2], de manera que podemos decir que en circunstancias normales, el algoritmo quicksort es más eficiente.

Una vez disponemos de una manera de expresar la complejidad algorítmica, podemos comenzar a analizar cualquier problema computacional que se nos ocurra y obtener de la misma manera la complejidad algorítmica, pero desgraciadamente, el mundo no es perfecto, y en algún momento se nos ocurrirá algún problema para el que no exista ningún algoritmo que se pueda resolver en un tiempo polinomial expresado con la notación anterior. Aquellos problemas para los que exista un algoritmo que lo soluciones en un tiempo polinomial se dice que pertenecen a la clase P mientras que aquellos problemas para los que no se puede diseñar un algoritmo que se resuelva en un tiempo polinomial se les conoce como problemas de clase NP
[3](nodeterministic polinomial problems). Si un problema de tipo NP se pude reformular en tiempo polinomial en otro problema NP, se dice que dicho problema pertenece a la clase NP-completo [4], de manera que si en algún momento se descubre un algoritmo que solucione en un tiempo polinomial dicho problema, automáticamente se habrán resuelto todos los demás problemas NP de dicha clase, puesto que se pueden convergen hacía este.

Aquellos problemas que pertenecen a la clase NP, son problemas que aunque teóricamente se conoce el algoritmo que lo resolvería, este necesitará muchísimo tiempo (por lo menos en el peor de los casos) encontrar la solución, haciendo que no sean viables. Como ejemplo de dichos problemas:

Problema del viajante (o entrutado) [5]: este problema consiste en que partiendo de un conjunto de ciudades C = {C₁, C₂, … C_n} deberemos encontrar una combinación que nos permita recorrerlas todas una y solo una vez minimizando la distancia totas recorrida. Como he dicho antes, el algoritmo que soluciones este problema, a priori es sencillo, simplemente deberemos comparar todas las posibles combinación de ciudades posibles y obtener aquella que minimiza la distancia. El problema radica en que a medida que aumenta el número n de ciudades la cantidad de combinaciones posibles de ciudades aumenta exponencialmente (n-1)!/2.

Para n = 10, unas 181.000 combinaciones.

Para n = 20, unas 10.000.000.000.000.000 soluciones posibles.

Para n = 50, … habrá que calcularlo, pero son muchísimas combinaciones posibles.

Problema de la asignación [6]
Problema de la mochila [7]
…

Queda claro, que para abarcar la solución de este tipo de problemas, se hace necesario cambiar de táctica, al no poder utilizar las soluciones tradicionales recorriendo todo el espacio de soluciones y devolviendo la mejor de todas. Como técnicas posibles para este tipo de problemas podemos citar:

Técnicas heurísticas: utilizan «meta-información» que ofrezca «conocimiento» al algoritmo hacer de lo buena que es una solución y así poder guiar la búsqueda en el espacio de soluciones, de manera que podamos obtener en un tiempo razonable una solución que aun no siendo la mejor, represente una solución buena.
Algoritmos genéticos: se inspiran en los mecanismos que la propia naturaleza utiliza para hacer evolucionar las especies haciendo que generación tras generación se mejoren los resultados.
Redes neuronales: podéis ver mi post sobre introducción a las redes neuronales.
Búsqueda tabú [8].
Optimización basada en colonias de hormigas [9].
…