Upload
daniel-roa
View
220
Download
3
Embed Size (px)
Citation preview
Complejidad de los Algoritmos
¿Qué es la complejidad de un
algoritmo? • Medida que expresa el tamaño de un
problema: • Recurso Tiempo. • Recurso Espacio.
Cuando hablamos de espacio
• Espacio en memoria asignado
• Interna (RAM)
• Externa (Disco)
Hablamos de Tiempo
Tiempo que necesita un algoritmo
Comportamiento de un Algoritmo
CASOS EXTREMOS
PEOR CASO
• Cuantas operaciones realiza un Algoritmo para garantizar una solución
CASO PROMEDIO
• Cantidad promedio de operaciones
• Cantidad de entradas promedio
EL OBJETIVO ES
MEDIR TIEMPO DE EJECUCION CUANDO LAS ENTRADAS CRECEN
T(n)
DIMENSIONES DEL PROBLEMA
SOLUCION ACORDE
PRUEBA DE UN ALGORITMO
COMPORTAMIENTO ASINTÓTICO
MEDIR EL COSTO
CLASIFICARLOS 0()
FAMILIAR • 0(1) Constante • 0(Logn) Logarítmico • 0(n) Lineal • 0(nlogn) Enelogarítmico • 0(n ) Polilogarítmico • 0(c ) Exponencial • O(n!) Factorial • 0(n ) Combinatorio
c
n
n