Eficiencia

Medida del uso de los recursos computacionales requeridos por la ejecución de un algoritmo en función del tamaño de las entradas.

T(n) Tiempo empleado para ejecutar el
algoritmo con una entrada de tamaño n

Tipos de análisis

¿Cómo medimos el tiempo de ejecución de un algoritmo?

Mejor caso
En condiciones óptimas (no se usa por ser demasiado optimista).

Peor caso
En el peor escenario posible (nos permite acotar el tiempo de ejecución).

Caso promedio
Caso difícil de caracterizar en la práctica.

Análisis probabilístico
Asume una distribución de probabilidad sobre las posibles entradas.

Análisis amortizado
Tiempo medio de ejecución por operación
sobre una secuencia de ejecuciones sucesivas