jueves, septiembre 17, 2009

Complejidad de los algoritmos (I)

Una cosa que no nos enseñan a los telecos es a programar bien. Vamos, que nos enseñan Java y C (u otros lenguajes, depende de la universidad) pero no tenemos la preparación que un Ingeniero Informático para estructurar un programa en condiciones.

Una cosa de la que había oído hablar pero que nunca vi en la carrera es la complejidad de un algoritmo programado. Es un concepto bastante básico y seguro que en algún plan de estudios de teleco se ve, pero no en la UPM. Intuitivamente ya había programado evitando ciertas malas costumbres, como bucles anidados, pero por experiencia propia y no porque me lo dijeran en la carrera.

Como quería aprender más del tema, estoy viendo unas clases del MIT sobre introducción a la programación, que además explican python, que es un lenguaje que me parece bastante adecuado para aprender (creo que he encontrado un sustituto para el Basic para enseñar a programar a mis hijos, cuando los tenga).

A lo que iba, ¿qué es la complejidad de un algoritmo? Definición para andar por casa: es lo que aumenta el tiempo de procesado si se aumenta la cantidad de datos de entrada del algoritmo. Por ejemplo, si tenemos un programa que calcula los números primos que hay desde 1 hasta un número que le demos (n) y aumentamos n, ¿cómo de lento se hace dicho programa?

La conclusión es que hay cuatro tiempos principales. El más intuitivo es el lineal. El tiempo aumenta linealmente con la cantidad de datos de la entrada. Por ejemplo, si le pedimos a nuestro programa los mil primeros primos y tarda 1 segundo y es lineal, podemos deducir que si le pedimos el primer millón de primos tardará mil segundos. Esto se denotaría O(n). Orden n, vamos, lineal.

Ahora bien, también está el tiempo cuadrático. Sería O(n²). Si tardamos en hacer los mil primeros primos 1 segundo, en hacer un millón tardamos un millón de segundos. Mucho peor.

También tenemos el caso logarítmico, en el que logramos una mejora considerable respecto al caso lineal. Esto sería O(log(n)) (donde log es el logaritmo en base 2). Con nuestro ejemplo anterior, si aumentamos de mil a un millón los primos que queremos, en el segundo caso tardaría unos 10 segundos. Una verdadera mejora respecto al caso lineal.

Ahora bien, también hay un caso horrible, y es el caso exponencial, donde O(2^n). ¡En este caso calcular el primer millón de primos llevaría 10^293 años! Un caso nefasto, ya que el universo no es tan antiguo. Hay que evitar este tipo de algoritmos siempre que se pueda.

En la siguiente entrada pondré ejemplos de algoritmos (con algo de código y también sin él) y su orden de complejidad.


Tags Technorati: , ,

2 comentarios:

Jorge dijo...

Pues se ve que cambiaron el temario, porque yo sí estudié en FPRG las complejidades de los algoritmos en temas de árboles de búsquedas y otras historias de ese tipo. Interesante en su momento y útil para eliminar posibles soluciones salvajes a ciertos problemas.

Alex dijo...

Sí, en FPRG se daban algoritmos de búsqueda (quicksort, bubblesort, megasort), pero como curiosidades, no con una formulación estricta de lo que es la complejidad de un algoritmo.

Quizá antes, que se usaba Pascal, se centraban más en algoritmos, y ahora (con Java) se centran más en programación orientada a objetos y modularidad.