RESUMEN, CONCLUSIONES Y RECOMENDACIONES

Bueno... al final no ha sido tan dificil. Resulta que un algoritmo que resuelve un problema con una determinada talla (por ejemplo, n) tarda un tiempo, en general, mayor en obtener la solución cuanto mayor es esa talla n (cosa que resulta obvia). La complejidad es una medida que nos da una idea de cómo es ese crecimiento, resultando que para la mayor parte de algoritmos, ese crecimiento se puede enmarcar en un determinado "orden", ya que todas las funciones que están en un orden crecen de manera similar cuando los valores de la talla se van haciendo grandes.

Para cada algoritmo, son interesantes un par de medidas de complejidad: en el peor caso (que señalamos con la notación O (Omicron, "Big-O"), y en el mejor, para el que utilizamos la notacion Ω (Omega). En especial, suele ser más imprescindible conocer el peor caso, ya que nos da una idea de qué es lo que puede pasar cuando las cosas van realmente mal.

Toda esta teoría de la complejidad, que tuvo un gran auge hace algunos años, ha sido criticada desde muchos puntos de vista. La verdad es que es muy útil en un nivel teórico, pero un nivel práctico tampoco conviene obsesionarse demasiado. Es necesario tener en cuenta que todo esto tiene que ver con límites cuando el tamaño de los problemas es muy grande y teniendo en cuenta el peor de los casos. A efectos prácticos, si estamos seguros de que el tamaño de nuestros problemas es pequeño, incluso un algoritmo con una complejidad "intratable" puede obtener soluciones en un tiempo razonable.

Además, muchos algoritmos con una elevada complejidad en el peor caso, resulta que no se comportan tan mal en la práctica, ya que muchas veces los problemas que se resuelven con él no son el peor caso. A veces, incluso se manipulan un poco los problemas para que nunca presenten el peor caso, o se aplican técnicas que ahorren trabajo al algoritmo (heurísticas, podas, etc). La complejidad del algoritmo es la misma, pero en promedio se comportan mucho mejor que lo que cabría esperar vista su complejidad en el peor caso, simplemente porque no se suele llegar al peor caso.

Por último, comentar que existen otras medidas de complejidad que las vistas hasta aquí, que son simplemente máximos y mínimos teóricos cuando la talla del problema tiende a un número muy grande. Y también, cuando un algoritmo se quiere probar "en la práctica" se aplican otran técnicas, principalmente teniendo en cuenta la probabilidad que tiene un problema en aparecer o no. Por ejemplo, los algoritmos de ordenación de arrays más sencillos tienen una complejidad máxima teórica de O(n²). Uno de los peores casos que se pueden presentar es que el array esté ordenado completamente al revés de como queremos... pero en una aplicación real es muy poco probable que esto ocurra... con lo que a veces la realidad no es tan mala, especialmente cuando los problemas no tienen una talla muy elevada.

Sobre la complejidad espacial que se mencionaba al principio podemos actuar de la misma manera, solo que en lugar de contar instrucciones, contamos las piezas de memoria dinámica que se utilizan. Ésto es, las que se solicitan del espacio del heap, de memoria secundaria, o las que que quedan atrapadas en la pila de ejecución cuando se usa recursividad. Sin embargo, su estudio suele tener menos interes, porque el tiempo es un recurso mucho más valioso que el espacio.

Este artículo está, con seguridad, repleto de incorrecciones formales. Lo sabemos... pero como decíamos al principio, no es nuestro objetivo describir formalmente la complejidad, sino simplemente intentar transmitir una idea intuitiva de lo que representa.

Si tienes interés en profundizar en el tema, hay mucha literatura al respecto, por ejemplo:

• Encuentro especialmente atractivo el libro de Giles Brassard y P. Bradley titulado "Fundamentos de algoritmia" (1996, Prentice-Hall), que puedes encontrar en cualquier librería especializada.
• También es muy interesante el libro que puedes descargar en línea titulado "Técnicas de diseño de algoritmos", de Rosa Guerequeta y Antonio Vallecillo.
• Unos breves apuntes de Jose A. Mañas en la Universidad Politécnica de Madrid muy fáciles de leer.
• Algunos artículos de wikipedia en español: cota superior asintótica , cota inferior asintótica , cota ajustada asintótica , análisis de algoritmos .
• La wikipedia en inglés tiene bastantes más artículos sobre el tema. Empieza con éste titulado Big-O notation y luego puedes seguir navegando por sus propias páginas.
• Por supuesto, Donald E. Knuth, uno de los pioneros en este campo, también habla de ello en su gran obra "The Art of Computer Programming" (Addison-Wesley), pero es una obra extensa (4 volúmenes y subiendo) no muy fácil de conseguir y a veces pesada de leer.