Análisis de eficiencia.

Índice:
❏ 1 Introducción
❏ 2 Análisis de Algoritmos O( n2 )
❏ 2.1 Burbuja
❏ 2.2 Inserción
❏ 2.3 Selección
❏ 3 Análisis de Algoritmos O( n * log(n) )
❏ 3.1 Mergesort
❏ 3.2 Heapsort
❏ 3.3 Quicksort
❏ 4 Análisis de Algoritmos O( n3 )
❏ 4.1 Floyd

❏ 5 Análisis de Algoritmos O( 2n )
❏ 5.1 Hanoi
❏ 6 Pruebas adicionales
❏ 6.1 Comparación entre los algoritmos de ordenación
❏6.2 Variaciones

Algorítmica Práctica 1 Grupo B

1 Introducción:
El uso de algoritmos en la informática, es esencial, es decir, para cualquier tarea 
relacionada con la informática, ya sea desde a nivel teórica, o a nivel práctico, es 
necesario tener un conocimiento básico sobre como analizar algoritmos, saber como mejorar un algoritmo, como comprarlo con otro para que los resultados sean realmente 
representativos o como mínimas modificaciones en un algoritmo pueden influir 
fuertemente en los resultados de nuestros softwares.
En esta práctica de la asignatura Algorítmica, vamos a analizar empíricamente 
varios algoritmos propuestos, de distintos órdenes de eficiencia, para luego ajustarlos a 
sus correspondientes órdenes de eficiencia teórica, para ver como coinciden. También haremos varias comparativas en algoritmos, y algunas modificaciones en el tratamiento 
de los algoritmos para ver cómo pueden variar con pequeños detalles, como variaciones 
en compilación, o en la ejecución en distintas computadoras.

Algorítmica Práctica 1 Grupo B

2 Análisis de Algoritmos O( n2 )  
:
Para analizar algoritmos con orden de eficiencia O( n2), vamos a usar 3 algoritmos 
clásicos de ordenación, burbuja, inserción y selección.
Para cada uno de ellos hemos realizado un programa que hace uso de cada uno 
de los algoritmos, y mediante el uso de macros CSH, vamos a lanzar varias veces cada 
programa con distintos tamaños de entrada, y obtendremos los tiempos de ejecución 
para cada uno de los tamaños propuestos.Para tomar los tiempos correspondientes a cada tamaño de entrada, hemos hecho 
uso de la librería Chrono de STL. La principal motivación para usar chrono es la precisión 
de esta librería para proporcionar tiempos.
 
Macro CSH

                   
salida.dat //Fichero de salida con los tamaños y los tiempos
@ i //variable que marca el número de veces que se ejecuta el programa y el tamaño de 
entrada./quicksort  //nombre del programa a ejecutar, en este ejemplo es quicksort, pero podría 
ser cualquiera.

Inclusión de Chrono

­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­­

Algorítmica Práctica 1 Grupo B

Uso de Chrono

2.1 Burbuja:
Tras lanzar 30 veces el programa que hace uso del algoritmo burbuja, los resultados son 
los siguientes:
Tamaño

Tiempo

600
1200 
1800 
2400 
3000 
3600 4200 
4800 
5400 
6000 
6600 
7200 
7800 
8400 
9000 
9600 
10200 
10800 
11400 
12000 
12600 
13200 
13800 
14400 
15000 
15600 
16200 
16800 
17400 
18000 

 0.001691
 0.00637
 0.012901
 0.019068
 0.026522
 0.034992
 0.044759
 0.0608
 0.08021
 0.094885
 0.11831
 0.141496
 0.167335
 0.19557
 0.226135
 0.2644
 0.301316
 0.334387
 0.369505
 0.413904 0.4613
 0.512699
 0.558593
 0.615241
 0.668583
 0.730312
 0.783715
 0.852297
 0.92242
 0.998692

Algorítmica Práctica 1 Grupo B

Estos tiempos han sido obtenidos lanzando el programa Burbuja en una 
computadora con la siguiente CPU:
CPU: Intel Cuad Core 2.4GHz
Usando GCC como compilador, sin optimizaciones en la compilación:
g++ ­o burbuja burbuja.cpp ­std=gnu++0x Gráfica de Burbuja

Para el ajuste híbrido de burbuja, hemos usado como ecuación teórica:
a2 * x2 + a1 * x + a0
Haciendo uso de GNUPlot y de su opción para hacer ajustes (fit) podemos obtener la 
siguiente gráfica con el ajuste añadido.

Algorítmica Práctica 1 Grupo B

Como se puede ver, el ajuste es prácticamente perfecto, lo cual nos indica, que las ...