Amortized Analysis
El análisis amortizado evalúa el límite superior del coste total de una secuencia de operaciones repartido entre cada operación, incluso si algunas son ocasionalmente costosas.
Propósito
Analizar el rendimiento promedio de estructuras de datos sobre secuencias de operaciones, como la expansión de arreglos dinámicos.
Mecanismo
Tres métodos: análisis agregado (coste total/operaciones), método contable (cobrar más a operaciones baratas para subsidiar las costosas), método potencial (función Φ mide la complejidad del estado). Inserción en arreglo dinámico: O(1) amortizado.
Casos de uso
- Análisis de estructuras de datos
- Garantías de rendimiento
- Diseño de algoritmos