Analisis del tiempo del algoritmo
Enviado por Alan Arriaga • 23 de Noviembre de 2021 • Apuntes • 651 Palabras (3 Páginas) • 166 Visitas
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.
...