El Análisis Amortizado se usa para algoritmos donde una operación ocasional es muy lenta, pero la mayoría de las otras operaciones son más rápidas.
En el Análisis Amortizado, analizamos una secuencia de operaciones y garantizamos un tiempo promedio en el peor de los casos, que es menor que el peor de una operación costosa en particular.
Las estructuras de datos de ejemplo cuyas operaciones se analizan utilizando el Análisis Amortizado son Tablas Hash, Conjuntos Disjuntos.
Consideremos un ejemplo de una simple inserción de tabla hash. ¿Cómo decidimos el tamaño de la mesa? Existe una compensación entre el espacio y el tiempo, si aumentamos el tamaño de la tabla hash, el tiempo de búsqueda se vuelve rápido, pero el espacio requerido se vuelve alto.
- Cómo organizar y buscar un árbol de búsqueda binario donde cada nodo tiene más de un campo de datos
- Además de la programación competitiva, ¿cómo aprender algoritmos?
- ¿Cuál es el algoritmo de aprendizaje automático más útil para Google?
- ¿Cuáles son los principios fundamentales de los algoritmos en la programación de computadoras?
- ¿Soy un mal programador si no puedo entender Towers of Hanoi?
La solución a este problema de compensación es usar Dynamic Table (o Arrays). La idea es aumentar el tamaño de la tabla cada vez que se llena. Los siguientes son los pasos a seguir cuando la tabla se llena.
1) Asigne memoria para una tabla de tamaño más grande, generalmente el doble de la tabla anterior.
2) Copie el contenido de la tabla anterior a la tabla nueva.
3) Libera la vieja mesa.
Si la tabla tiene espacio disponible, simplemente insertamos un nuevo elemento en el espacio disponible.
¿Cuál es la complejidad temporal de n inserciones usando el esquema anterior?
Si utilizamos un análisis simple, el costo del peor caso de una inserción es O (n). Por lo tanto, el costo del peor caso de n inserciones es n * O (n) que es O (n-cuadrado).
Este análisis proporciona un límite superior, pero no un límite superior ajustado para n inserciones, ya que todas las inserciones no requieren tiempo Θ (n).
Entonces, utilizando el Análisis Amortizado, podríamos probar que el esquema de Tabla Dinámica tiene un tiempo de inserción O (1), que es un gran resultado utilizado en el hash. Además, el concepto de tabla dinámica se utiliza en vectores en C ++, ArrayList en Java.
Las siguientes son algunas notas importantes.
1) El costo amortizado de una secuencia de operaciones puede verse como gastos de una persona asalariada. El gasto mensual promedio de la persona es menor o igual al salario, pero la persona puede gastar más dinero en un mes en particular comprando un automóvil o algo así. En otros meses, él o ella ahorra dinero para el mes costoso.
2) El Análisis Amortizado anterior realizado para el ejemplo de matriz dinámica se llama Método agregado . Hay dos formas más poderosas de hacer análisis Amortizados llamados Método de contabilidad y método potencial .
3) El análisis amortizado no implica probabilidad. También existe otra noción diferente de tiempo promedio de ejecución de casos en el que los algoritmos usan la aleatorización para hacerlos más rápidos y el tiempo de ejecución esperado es más rápido que el peor de los casos. Estos algoritmos se analizan mediante análisis aleatorio. Ejemplos de estos algoritmos son la clasificación rápida aleatoria, la selección rápida y el hash.
Fuentes:
Berkeley Lecture 35: Análisis Amortizado
Lección 13 del MIT: Algoritmos amortizados, duplicación de tablas, método potencial
http://www.cs.cornell.edu/course…
