Analisis de algoritmos . Predecir como se comporta el algoritmo, en cuanto al consumo de recursos

Analisis de algoritmos

Predecir como se comporta el algoritmo, en cuanto al consumo de recursos.

Ej. Cuanto tiempo va a necesitar para resolver un caso dado.

Recursos:

- Tiempo.

- Memoria.

- Memoria secundaria.

- Ancho de banda

Analisis del tiempo del algoritmo.

¿Tiempo en que sistema?

Sistema:

- Hardware

• CPU

• Memoria

• Motherboard

• Almacenamiento secundario

• …

- Software

• S. O.

• Lenguaje

• Compilador o Interprete

• Bios

• …

- Humaware

• Adminastrador

• Programador

• Usuario

t ( n ) : Tiempo de ejecución de un algoritmo para una entrada de tamaño n.

n: Tamaño de la entrada en bits. Podría usarse un número adecuado.

Principio de Invarianza

El tiempo de ejecución del mismo algoritmo en dos sistemas diferentes, varía solo por una constante multiplicativa.

t1 ( n ) = c * t2 ( n )

t1 ( n ), t2 ( n ) € O ( f ( n ) )

O ( f ( n ) ) representa la velocidad del creciemiento del tiempo de ejecución con respecto a la entrada.

O ( n ) : Orden lineal.

O ( n5 ) : Pertenece a los ordenes polinómicos.

O ( 5n ) : Pertenece a los ordenes exponenciales.

O ( n ) O ( n2 ) O ( n5 )

k t ( k ) t ( k ) t ( k )

2k 2t ( k ) 4t ( k ) 32t ( k )

10k 10t ( k ) 100t ( k ) 100,000t ( k )

¿Por qué?

Problema de las constantes ocultas.

A veces, un algoritmo de orden alto es mas rápido, que un algoritmo de orden bajo; en casos pequeños.

A veces, el orden no es una buena indicación del tiempo de ejecución.

Se presenta en casos pequeños.

t1 ( n ) = n2 + 8n – 15 € O ( n2 )

t2 ( n ) = 1000n + 2500 € O ( n )

n t1 ( n ) t2 ( n )

1 -6 3,500

10 165 12,500

100 10,785 102,500

1,000 1’007,985 1’002,500

10,000 100’079,985 10’002,500

¿Como se hace el analisis?

El tiempo de ejecución no sólo depende del tamaño de la entrada, tambien depende de la entrada misma. Ej. t( k ) puede cambiar dependiendo de la entrada.

¿Cual caso utilizar?

- Peor Caso.

El caso que mas tiempo necesita para ejecutarse.

Ventaja: Es fácil de indentificar.

Desventaja: No es siempre es representativo.

- Caso Promedio.

El promedio de todos los casos. Usualmente se usa una aproximación, el promedio de una muestra, la moda, el promedio entre el peor caso y el mejor caso ( caso medio ).

Desventaja: Es dificil de calcular.

Ventaja: Es representativo, muestra lo que puedes esperar de un algoritmo para una entrada aleatoria.

Hay dos grandes filosofías de como hacer el análisis.

- Análisis a-posteriori.

Despues de implementar. Implementar el algoritmo y simular su funcionamiento, para medir el tiempo de ejecución.

Enfoque estadístico.

- Análisis a-priori.

Antes de implementar. Analizarlo muy pronto en el proceso de creación del algoritmo para no perder tiempo.

Tarea: Analisis A-posteriori.

• Algoritmos:

◦ Selección

◦ Burbuja

◦ Inserción

◦ Shell ( tradicional )

◦ QuickSort

• Valores a medir:

◦ Tiempo de ejecución

◦ # asignaciones al arreglo.

◦ # comparaciones de elementos del arreglo.

• Tipos de archivos.

◦ Archivo ordenado ( 1 )

◦ Archivo inversamente ordenando ( 1 )

◦ Archivo aleatorios ( 10 )

...