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

...