Análisis Amortizado

El análisis amortizado delimita el costo promedio por operación en una secuencia de operaciones en el peor de los casos, demostrando que las operaciones ocasionalmente costosas pueden resultar económicas cuando su costo se distribuye entre muchas operaciones de bajo costo.

Definition

El análisis amortizado es un método para acotar el costo total de una secuencia de operaciones en una estructura de datos y dividirlo por el número de operaciones, lo que produce un costo amortizado por operación que se mantiene en el peor de los casos a lo largo de toda la secuencia, incluso cuando las operaciones individuales difieren ampliamente en costo.

Scope

Este tema abarca las tres técnicas estándar del análisis amortizado —el método agregado, el método de contabilidad (o del banquero) y el método potencial— y su aplicación a estructuras de datos cuyas operaciones individuales varían en costo, como los arreglos dinámicos, los contadores binarios, los árboles splay y la estructura de conjuntos disjuntos (union-find). Distingue el costo amortizado del costo promedio y del costo por operación en el peor de los casos.

Core questions

• ¿En qué se diferencia el costo amortizado del costo por operación en el peor de los casos y del costo promedio?
• ¿Cómo delimita el método agregado el costo total de una secuencia de operaciones?
• ¿Cómo asigna el método de contabilidad créditos para pagar operaciones costosas posteriores?
• ¿Cómo utiliza el método potencial una función potencial para suavizar los costos?
• ¿Qué estructuras de datos se basan en garantías amortizadas en lugar de límites por operación?

Key concepts

• costo amortizado
• método agregado
• método de contabilidad (del banquero)
• método potencial
• función potencial
• duplicación de arreglo dinámico
• incremento de contador binario
• union-find con compresión de rutas

Key theories

Método potencial

El método potencial asigna un potencial no negativo al estado de la estructura de datos; el costo amortizado de una operación es su costo real más el cambio en el potencial, de modo que las operaciones económicas acumulan potencial que paga por las operaciones costosas posteriores.

Método de contabilidad (del banquero)

El método de contabilidad cobra algunas operaciones más de su costo real, almacenando el excedente como crédito en los elementos de la estructura de datos para pagar futuras operaciones costosas, asegurando que el crédito nunca sea negativo.

Clinical relevance

El análisis amortizado explica por qué muchas estructuras ampliamente utilizadas son eficientes en la práctica a pesar de operaciones ocasionalmente costosas: los arreglos dinámicos (listas redimensionables), las tablas hash que se rehash, la operación union-find utilizada en algoritmos de conectividad y de árbol de expansión mínima, y las estructuras autoajustables como los árboles splay, todas se basan en garantías amortizadas en lugar de garantías por operación.

History

El término y el marco sistemático para el análisis amortizado fueron introducidos por Robert Tarjan en 1985, basándose en argumentos ad hoc anteriores. La técnica fue fundamental para analizar las estructuras de datos autoajustables (árboles splay, montículos de Fibonacci) desarrolladas por Tarjan y Sleator en la década de 1980.

Key figures

• Robert Tarjan
• Daniel Sleator

Seminal works

• tarjan1985amortized
• cormen2009

Frequently asked questions

¿Es el costo amortizado lo mismo que el costo promedio?

No. El costo promedio es una expectativa sobre una distribución de probabilidad de las entradas y puede ser violado por una entrada desafortunada. El costo amortizado es una garantía en el peor de los casos sobre una secuencia de operaciones sin suponer aleatoriedad: el costo total de cualquier secuencia de este tipo está acotado, por lo que el promedio por operación siempre se mantiene.

¿Por qué añadir a un arreglo dinámico es O(1) amortizado cuando el redimensionamiento es O(n)?

Porque el arreglo generalmente duplica su capacidad, los redimensionamientos son raros en relación con las adiciones, y el trabajo total de copiado en una secuencia de n adiciones es proporcional a n. Distribuido entre todas las adiciones, eso da un costo amortizado constante, aunque un solo redimensionamiento sea lineal.