View
251
Download
0
Category
Preview:
DESCRIPTION
Práctica 1
Citation preview
©
Práctica 1: Análisis de eficiencia de algoritmos
Alberto, Juanmi, Manu, Migue & Mariano
1
Algorítmica
©
ÍndicePráctica 1: Análisis de eficiencia de algoritmos
1. Objetivo
2. Cálculo del tiempo teórico
3. Cálculo de la eficiencia empírica
4. Cálculo de la eficiencia híbrida
2
©
1. ObjetivoPráctica 1: Análisis de eficiencia de algoritmos
• El objetivo de esta práctica es que el estudiante comprenda la
importancia del análisis de la eficiencia de los algoritmos y se
familiarice con las formas de llevarlo a cabo.
• Para ello se mostrará cómo realizar un estudio teórico,
empírico e híbrido.
• Cada equipo de estudiantes deberá realizar los análisis
empíricos e híbridos de los algoritmos que se detallan más
adelante.
3
©
2. Cálculo del tiempo teóricoPráctica 1: Análisis de eficiencia de algoritmos
• A partir de la expresión del algoritmo, se aplicarán las reglas
conocidas para contar el número de operaciones que realiza
un algoritmo: T(n)
• Tras obtener la expresión analítica de T (n), calcularemos el
orden de eficiencia del algoritmo empleando la notación O().
4
©
3. Cálculo de la eficiencia empíricaPráctica 1: Análisis de eficiencia de algoritmos
Medimos los recursos empleados (tiempo) para cada tamaño dado
de las entradas
• Ordenación: el tamaño viene dado por el número de componentes
del vector a ordenar
• Floyd: calcula los caminos mínimos entre todos los pares de nodos en
un grafo dirigido, el tamaño es el número de nodos del grafo.
• Fibonacci: el tamaño es el valor de n en la sucesión de Fibonacci.
Se ha creado un script para automatizar la ejecución los distintos
algoritmos con diferentes tamaños de entradas.
Para asegurar la precisión en el cálculo del tiempo de ejecución,
haremos uso de la biblioteca chrono de la STL.
5
©
4. Cálculo de la eficiencia híbridaPráctica 1: Análisis de eficiencia de algoritmos
Con el propósito de conocer de manera más exacta la ecuación del
tiempo de ejecución para una situación concreta, llevaremos a
cabo el cálculo de la eficiencia híbrida.
A la hora de realizar el cálculo teórico, obtenemos la expresión
general de la ecuación, pero asociada a cada término de esta
expresión, aparece una constante de valor desconocido.
La forma de averiguar estos valores es ajustar la función a un
conjunto de puntos: los obtenidos a partir del cálculo empírico en
el apartado anterior, de manera que aplicaremos una regresión por
mínimos cuadrados para el ajuste mediante gnuplot.
Las funciones de regresión utilizadas son:
• Algoritmos cuadráticos: 𝑎0𝑥2 + 𝑎1𝑥 + 𝑎2
• Algoritmos logarítmicos: 𝑎0𝑥 + 𝑎1𝑥 log 𝑥
• Algoritmos cúbicos: 𝑎0𝑥3 + 𝑎1𝑥
2 + 𝑎2𝑥 + 𝑎3• Algoritmo recursivo (exponencial): 𝑎0 𝑎1
𝑥 + 𝑎2 6
©
4. Cálculo de la eficiencia híbridaPráctica 1: Análisis de eficiencia de algoritmos
Por último, mostramos a continuación las tablas y gráficas
obtenidas de los diferentes algoritmos:
• Comparación entre cada una de las curvas de los diferentes
algoritmos cuadráticos y los logarítmicos.
• Comparación de algunos algoritmos con y sin opciones de
optimización.
7
Recommended