Python - Análisis amortizado
El análisis amortizado implica estimar el tiempo de ejecución de la secuencia de operaciones en un programa sin tener en cuenta el intervalo de distribución de datos en los valores de entrada. Un ejemplo simple es encontrar un valor en una lista ordenada más rápido que en una lista sin clasificar. Si la lista ya está ordenada, no importa qué tan distribuidos estén los datos. Pero, por supuesto, la longitud de la lista tiene un impacto, ya que decide la cantidad de pasos que debe seguir el algoritmo para obtener el resultado final.
Entonces vemos que si el costo inicial de un solo paso para obtener una lista ordenada es alto, entonces el costo de los pasos posteriores para encontrar un elemento se vuelve considerablemente bajo. Por lo tanto, el análisis amortizado nos ayuda a encontrar un límite en el peor tiempo de ejecución para una secuencia de operaciones. Hay tres enfoques para el análisis amortizado.
Accounting Method- Implica asignar un costo a cada operación realizada. Si la operación real finaliza antes que el tiempo asignado, se acumula algún crédito positivo en el análisis. En el escenario inverso, será crédito negativo. Para realizar un seguimiento de estos créditos acumulados, utilizamos una estructura de datos de pila o árbol. Las operaciones que se llevan a cabo anticipadamente (como ordenar la lista) tienen un costo amortizado alto, pero las operaciones que se retrasan en la secuencia tienen un costo amortizado menor a medida que se utiliza el crédito acumulado. Entonces, el costo amortizado es un límite superior del costo real.
Potential Method- En este método, el crédito ahorrado se utiliza para operaciones futuras como función matemática del estado de la estructura de datos. La evaluación de la función matemática y el costo amortizado deben ser iguales. Entonces, cuando el costo real es mayor que el costo amortizado, hay una disminución en el potencial y se utiliza para operaciones futuras que son costosas.
Aggregate analysis - En este método estimamos el límite superior del costo total de n pasos. El costo amortizado es una simple división del costo total y el número de pasos (n).