Analisis De Algoritmos

Análisis de complejidad
©César Arturo Cepeda García. Última modificación 23 abril 2004.
________________________________________
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 apartir 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 muyrá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 delalgoritmo, 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 deordenar 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 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 laentrada, 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!
________________________________________
ORDENACION POR INSERCION
La ordenación por inserción es un algoritmo eficiente para ordenar pequeñas cantidades de elementos. La ordenación por inserción funciona de la misma manera que la mayoria de las personas ordena una mano de barajas. Se comienza con una la mano izquierda vacia, yla mano de barajas, boca abajo en la mesa. Entonces vamos recogiendo una a una las barajas de la mesa y las insertamos en la posición correcta en la mano izquierda. Para encontrar la posición correcta, comparamos la nueva baraja con las que tenemos en la mano, de derecha a izquierda. En todo momento, las barajas que tenemos en la mano izquierda se encuentran ordenadas.
A continuaciónpresentamos un pseudocódigo para implementar el ordenamiento por inserción, nuestro procedimiento toma como entrada un arreglo A[1..n] que contiene una secuencia de elementos de longitud n.
ORDENAMIENTO-INSERCION (A)
1 desde j:=2 hasta Longitud(A) haz inicio
2 llave:=A[j]
3 i:=j - 1
4 mientras (i > 0) y (A[i] > llave) haz inicio
5 A[i + 1] := A[i]
6i:=i - 1
7 fin-mientras
8 A[i + 1]:=llave
9 fin-desde
El código funciona de la siguiente manera, inicialmente tenemos el arreglo A con los elementos desordenados. Como se explico en el primer párrafo la ordenación por inserción busca siempre tener ordenada la parte izquierda del arreglo, e ir tomando uno a uno los elementos del lado derecho para insertarlos en su posición....