INTRODUCCION
Cuando se analiza y compara el desempeño de diferentes algoritmos, se presta una especial atención al tiempo de corrida del algoritmo. El tiempo de corrida de un algoritmo, se entiende como el tiempo que le toma al algoritmo calcular el resultado a partir de los datos de entrada.
¿Por qué es importante el tiempo de corrida de un algoritmo? Porque si conocemos o al menos tenemos una idea del tiempo de corrida de un algoritmo podemos saber que tanto va a tardar en entregarnos la respuesta, y podemos decidir, si la esperamos, nos vamos a tomar un café o si mejor regresamos después de una semana.
Aunque las computadoras de hoy en día son muy rápidas comparadas con sus similares de hace algunos años, y son capaces de llevar a cabo millones de operaciones en un segundo, resulta fácil encontrar ejemplos de problemas y soluciones que tardarían años en solucionarse.
Cuando se analiza el tiempo de corrida de un algoritmo, mas que el tiempo exacto que tardará el algoritmo en milisengudos, lo que importa es la función de crecimiento del algoritmo, la función de crecimiento de un algoritmo, nos da una idea de que tanto aumentará el tiempo de corrida según aumente el tamaño de la entrada. Por lo general, la función de crecimiento de un algoritmo se expresa como la multiplicación de una constante y una función que depende del tamaño de la entrada, es decir, c f(n) donde n es el tamaño de la entrada.
Tomemos por ejemplo el problema de ordenar una lista de números. Se tiene un conjunto de números A{x1, x2, ... , xn} un algoritmo de ordenación debe entregar como salida una permutación del conjunto A tal que xi <= xj para cualquier i < j. Es decir debe ordenar los números del conjunto de chico a grande.
Ordenar una lista de números es quizá la operación más común en las computadoras, cientos de programas ordenan datos para poder trabajar con ellos, debido a eso, la cantidad de algoritmos de ordenación que hay es muy grande, así como el tiempo que se ha dedicado a estudiarlos, muy extenso. Para este apunte de análisis de complejidad vamos a estudiar principalmente 2 de los algoritmos más famosos de ordenación. La ordenación por inserción(Insertion Sort) y la ordenación por mezcla(Merge Sort).
La ordenación por inserción tiene una función de crecimiento f(n) = n2, mientras que la ordenación por mezcla tiene una función de crecimiento f(n) = n lg n donde lg n representa el logaritmo base 2 de n. Para demostrar el porque es necesario estudiar el análisis de complejidad, comparemos estos dos algoritmos. Supongamos que el mejor programador del mundo implemento la ordenación por inserción en lenguaje máquina logrando una constante de 2, por lo que el tiempo total de corrida será T=2 n2, donde n representa la cantidad de números que queremos ordenar. Ahora supongamos que un programador promedio implementa la ordenación por mezcla utilizando un lenguaje de alto nivel obteniendo una constante de 50, por lo tanto el tiempo total de corrilda de la ordenación por mezcla será de T=50 n lg n. Supongamos además que tenemos una computadora capaz de ejecutar 10,000,000 de operaciones por segundo.
Comparemos ahora el desempeño de ambas soluciones, supongamos primero que queremos ordenar 1000 números.
Tinsersión = 2 (1000)2 = 2,000,000 => 0.2 segundos
Tmezcla = 50 (1000) (11) = 550,000 => 0.055 segundos
Como se observa, el desempeño de la ordenación por mezcla es mucho mejor, la diferencia se va haciendo más drástica conforme varía el tamaño de la entrada, por ejemplo si quisieramos ordenar 100,000,000 de números los tiempos serían
Tinsersión = 2 (100000000)2 = 20,000,000,000,000,000 un poco mas de 63 años!!!!!!!
Tmezcla = 50 (100000000) (27) = 135,000,000,000 3 horas con 45 minutos.
Mientras que la ordenación por inserción tomaria todo el resto de sus vidas, la ordenación por mezcla apenas y necesitaria menos de 4 horas. Por eso vale la pena analizar un algoritmo antes de implementarlo!
Usuarios que han visto este tema también han visto...
- Problemas económicos para la Wikipedia
- Colores que ayudan a navegar
- Permisos, usuarios y grupos en Windows Vista
- Como elegir el color de la tipografia
- Las contraseñas más habituales
- Versión imprimible de este documento
- Enviar por e-mail este documento
