¿Qué es el análisis amortizado? ¿Y cómo puede ayudarme a lograr garantías de rendimiento en el peor de los casos en mis programas?
Estaba leyendo que las siguientes técnicas pueden ayudar al programador a lograr las garantías de rendimiento en el peor de los casos (es decir, en mis propias palabras: garantizar que el tiempo de ejecución de un programa no exceda el tiempo de ejecución en el peor reparto):
- Algoritmos aleatorizados (por ejemplo, el algoritmo de clasificación rápida es cuadrático en el peor de los casos, pero ordenar aleatoriamente la entrada da una garantía probabilística de que su tiempo de ejecución es linealitmico)
- Secuencias de operaciones (nuestro análisis debe tener en cuenta tanto los datos como la secuencia de operaciones realizadas por el cliente)
- Análisis Amortizado (otra forma de proporcionar una garantía de desempeño es amortizar el costo, haciendo un seguimiento del costo total de todas las operaciones, dividido por el número de operaciones. En esta configuración, podemos permitir algunas operaciones costosas, manteniendo el costo promedio de operaciones bajas. En otras palabras, distribuimos el costo de las pocas operaciones costosas, asignando una parte de ellas a cada una de una gran cantidad de operaciones económicas)
El autor mencionó el uso del cambio de tamaño de la estructura de datos de la matriz para Stack como un ejemplo de cómo lograr un análisis amortizado, pero todavía no entiendo qué es el análisis amortizado y cómo se puede implementar realmente (¿estructura de datos? ¿Algoritmo?) Para lograr lo peor -cast garantías de rendimiento
fuente