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:
- Análisis global determina el límite superior T (n) en el coste total de una secuencia de n operaciones, y luego calcula el coste medio a T (n) / n.
- Método Contable permite determinar el costo individual de cada operación, que combina su inmediato tiempo de ejecución y su influencia en el tiempo de ejecución de las futuras operaciones. Generalmente, muchos operaciones de corta duración acumulan una "deuda" de situación desfavorable en pequeños incrementos, mientras que las operaciones de larga duración disminuyen drásticamente.
- Método potencial es como el método, pero las operaciones tempranas que sobrecargan la cuente pueden ser compensadas cobrando menos de la cuenta más tarde.
Referencias
- Esta obra contiene una traducción derivada de «Amortized analysis» de Wikipedia en inglés, publicada por sus editores bajo la Licencia de documentación libre de GNU y la Licencia Creative Commons Atribución-CompartirIgual 3.0 Unported.
- Allan Borodin y Ran El-Yaniv (1998). Online Computation and Competitive Analysis. Cambridge University Press. pp. 20,141.
- Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest y Clifford Stein. Introduction to Algorithms, Segunda edición. MIT Press and McGraw-Hill, 2001. ISBN 0-262-03293-7. Capítulo 17: Amortized Analysis, págs.405–430.