Análisis de amortización

En ciencias de la computación, especialmente el análisis de algoritmos, el análisis de amortización considera el promedio de tiempo de ejecución por más de una operación en el peor de los casos, la secuencia de las operaciones. El análisis de amortización difiere del promedio de rendimiento en caso de que no se trate de probabilidad; el análisis de amortización garantiza la operación por más tiempo tomando en cuenta el peor de los casos en el rendimiento.

El método requiere el conocimiento de esta serie de operaciones que son posibles. Este es el caso más común en estructuras de datos, que han estado que persiste entre las operaciones. La idea básica es que el peor de los casos la operación puede alterar el estado de tal manera que el peor de los casos no puede ocurrir de nuevo por un largo tiempo, por lo tanto queda "amortizado" su costo.

Como ejemplo simple, en una implementación específica de array dinámicos, doblamos el tamaño del array cada vez que se rellene. Debido a esto, es necesario reasignar el array, y en el peor de los casos puede requerir una inserción O (n). Sin embargo, una secuencia de n inserciones siempre se puede hacer en O (n) tiempo, de modo que el tiempo de amortización por operación es O (n) / n = O (1).

El análisis del caso promedio y análisis probabilístico no son lo mismo en análisis de amortización. En análisis del caso promedio, estamos en un promedio de todas las posibles entradas, en el análisis probabilístico, estamos en un promedio de todas las posibles opciones al azar; en el análisis de amortización, estamos en promedio más de una secuencia de operaciones. Amortizan análisis asume el peor de los casos de entrada y, normalmente, no permite opciones al azar.

Existen varias técnicas utilizadas en el análisis amortizado:

---