Saltar al contenido principal

Análisis Amortizado

--> imagen de cuadrado conteniendo dos barritas como ejemplo de versus entre análisis amortizado y peor caso

El análisis amortizado es una técnica que permite analizar el costo de una secuencia de nn operaciones, cuando éste es menor de lo que se obtiene tomando el peor caso de una operación y multiplicándolo por nn. En este caso, diremos que el costo amortizado de cada operación es el costo total de la secuencia de operaciones dividido nn. Note que esto no es lo mismo que análisis de caso promedio: se considera la peor secuencia posible de nn operaciones (aunque, independientemente, podríamos hablar de costo promedio amortizado).

Veremos tres técnicas de análisis amortizado. Según el caso, puede ser más natural utilizar una que otra. Las ejemplificaremos con algunos casos sencillos. Después veremos algunos algoritmos y estructuras de datos relevantes donde el análisis amortizado es fundamental para comprender sus costos.