Eficiencia Algorítmica y Notación Asintótica

Este artículo es una breve introducción a uno de los conceptos básicos de la algorítmica: La eficiencia. Para ello se introducirá (y justificará) brevemente una herramienta matemática muy útil en este campo llamada Notación Asintótica.

Algoritmos

Un algoritmo es un conjunto no ambiguo, finito y ordenado de instrucciones que sirven para resolver un problema dado. Por ejemplo, el algoritmo para salir de una habitación consiste en dirigirse hacia la puerta, abrirla y atravesarla.

Dependiendo del nivel de detalle de las instrucciones tenemos algoritmos de alto nivel o algoritmos de bajo nivel. Los primeros detallan las instrucciones sin entrar en los detalles (como he hecho yo en el ejemplo anterior). Los segundos son mucho más específicos y por lo tanto mucho más complejos: evalúa una ruta libre de obstáculos hasta la puerta, recorre dicha ruta, (si la puerta está cerrada) busca en tu memoria cómo funciona el modelo de pomo que hay en la puerta, ejecuta el algoritmo de apertura de la puerta (para ese pomo), pasa por debajo del marco una vez despejado el camino, etc…

Un algoritmo debe llevar a cabo la tarea teniendo en cuenta todos los factores que la pueden afectar. Por ejemplo, no estaría de más fijarse en qué hay detrás de la puerta antes de cruzarla.

Eficiencia

Un buen algoritmo es aquel que resuelve mejor el problema. Es decir, el que de entre todas las soluciones posibles encuentra la mejor y lo hace sin cometer errores ni desperdiciar recursos. En ocasiones, la naturaleza del problema hace necesario sacrificar alguno de estos factores para mejorar algún otro: Por ejemplo, los Métodos Heurísticos sacrifican un poco la calidad de las respuestas por tal de tardar menos en encontrarlas. Las técnicas de Programación Dinámica sacrifican un poco de memoria de tu ordenador para mejorar la velocidad con la que se ejecuta un programa. En muchos otros casos se sacrifica el tiempo para que el algoritmo sea más claro y sencillo de llevar a cabo.

Para formalizar este concepto y poder comparar diversos algoritmos entre sí se acostumbra a usar criterios como el número de operaciones realizadas o la memoria que consume un programa de media cada vez que se ejecuta un determinado algoritmo.

En ambos casos, sobretodo en el temporal, se habla de algoritmos eficientes cuando nos hallamos ante los algoritmos que gastan menos recursos para resolver (con el mismo nivel de calidad) un problema dado.

Notación asintótica

Ahora bien, la eficiencia de un algoritmo se acostumbra a expresar como una función del tamaño de la entrada: Si estamos en una habitación con 100 puertas y detrás de cada una de ellas hay un número, el algoritmo para encontrar el mínimo de esos números tardará 100 operaciones de abrir puerta y leer número en finalizar. Si, por el contrario, hubiese 100.000 puertas tardaría, como es obvio, 1.000 veces más que antes.

Así, en general, podemos decir que el algoritmo que consiste en abrir las puertas una por una y leer el número (memorizando siempre cual es el mínimo de los leídos hasta ahora) es un algoritmo que realiza un número de operaciones directamente proporcional al número de puertas. Esto puede expresarse de manera compacta diciendo que es un algoritmo O(n) donde n es el número de puertas y la O() implica proporcionalidad directa.

Complejidad Algorítmica Así, en orden creciente de complejidad tenemos (entre otros):

  • O(1) (algoritmos constantes)
  • O(log(n)) (algoritmos logarítmicos)
  • O(√n)
  • O(n) (algoritmos lineales)
  • O(n·lg(n))
  • O(n²) (algoritmos cuadráticos)
  • O(n³) (algoritmos cúbicos)
  • O(n^k) (algoritmos polinómicos)
  • O(k^n) (algoritmos exponenciales)

Hay muy pocos algoritmos que tarden un tiempo constante en ejecutarse.

Por otra parte, todo aquel algoritmo que sea más rápido que un algoritmo lineal se considera un algoritmo rapidísimo (especialmente los logarítmicos).

Un tiempo de ejecución lineal o O(n·lg(n)) es normalmente lo mejor que se puede obtener para resolver muchos problemas y a partir de O(n³) para arriba el cómputo puede volverse intratable incluso para los ordenadores más potentes.

Teoría vs práctica

La mayoría de algoritmos se consideran eficientes o ineficientes en comparación con el mejor algoritmo conocido para resolver el mismo problema. Es decir, un algoritmo O(n·log(n)) puede ser considerado poco eficiente simplemente porque existe otro algoritmo que hace lo mismo en tiempo O(√n).

Por otra parte existen, para algunos casos muy concretos, problemas para los que hay una cota inferior en cuanto a complejidad se refiere. Así, está demostrado matemáticamente que los algoritmos de ordenación (de los que hablaré mañana) tardan un mínimo de O(n·log(N)) operaciones en ordenar n elementos. Por lo tanto no importa cómo de ingeniosos seamos porque nunca jamás podremos ordenar más rápido.

Se podría considerar, en consecuencia, que como ya conocemos algún algoritmo de ordenación O(n·log(n)) no es necesario seguir investigando en este campo, pero mañana veremos que todavía queda mucho por hacer en él.

BOLAEXTRA: Este post pertenece a una serie especial de 5 artículos relacionados:

  1. Eficiencia Algorítmica y Notación Asintótica
  2. Algoritmos de Ordenación
  3. Algoritmos de Ordenación Adaptativos
  4. Algoritmos de Pseudoordenación
  5. Medidas del Orden de una Secuencia

Te recomiendo encarecidamente que leas los 5 en orden ya que cada uno de ellos depende fuertemente de los anteriores.

Escrito en 07/12/09 10:49 por Carlos Luna en las categorías:

Comentarios

Gravatar.com se ha roto

Hiya!

Como puntualización, decir que son los algoritmos de ordenación por comparación los que tienen una cota inferior en complejidad de O(n·log(n)), pero no todos funcionan así. Sin embargo, estoy completamente de acuerdo que la mayoría de veces se usan estos algoritmos para ordenar cosas.

Otro detallito: O(f(n)) significa “crece como mucho como algo proporcional a f(n)”. La proporcionalidad directa se denota por la theta.

Tonterías a parte, muy buen post. Seguiré con ganas esta serie de cinco ;)

Pere Daniel | 07/12/09 18:13 | #
Gravatar.com se ha roto

@Pere Daniel: Totalmente de acuerdo en ambas puntualizaciones pero creo que no retocaré el texto porque la primera queda implícitamente explicada con el post de mañana y la segunda complica demasiado la explicación para alguien que no conozca el tema de antemano.

Carlos Luna | 07/12/09 21:55 | #

Deja un Comentario

Quizás quieras usar textile para dar formato a tu comentario.

"linktext":http://       _em_       *strong*       -strike-       ^sup^       ~sub~
bq. Blockquote       # Lista numerada       * Lista no-numerada       ==html crudo, sin textile==

(no será mostrado) (http://...)