El análisis amortizado se utiliza para algoritmos en los que una operación ocasional es muy lenta, pero la mayoría de las demás operaciones son más rápidas. En Análisis amortizado, analizamos una secuencia de operaciones y garantizamos un tiempo promedio en el peor de los casos que es menor que el tiempo en el peor de los casos de una operación particularmente costosa.
Las estructuras de datos de ejemplo cuyas operaciones se analizan mediante el análisis amortizado son tablas hash, conjuntos disjuntos y árboles separados.
Consideremos un ejemplo de inserciones simples de tablas hash. ¿Cómo decidimos el tamaño de la mesa? Existe una compensación entre el espacio y el tiempo, si hacemos que el tamaño de la tabla hash sea grande, el tiempo de búsqueda se reduce, pero el espacio requerido se vuelve alto.
La solución a este problema de compensación es usar Dynamic Table (o Arrays) . La idea es aumentar el tamaño de la mesa cada vez que se llene. Los siguientes son los pasos a seguir cuando la mesa se llena.
1) Asigne memoria para un tamaño de tabla más grande, generalmente el doble de la tabla anterior.
2) Copie el contenido de la tabla anterior en una tabla nueva.
3) Liberar la mesa antigua.
Si la tabla tiene espacio disponible, simplemente insertamos un nuevo elemento en el espacio disponible.
¿Cuál es la complejidad temporal de n inserciones utilizando el esquema anterior?
Si usamos un análisis simple, el costo de inserción en el peor de los casos es O(n). Por lo tanto, el costo en el peor de los casos de n inserciones es n * O(n) que es O(n 2 ). Este análisis proporciona un límite superior, pero no un límite superior estricto para n inserciones, ya que todas las inserciones no toman Θ(n) tiempo.
Entonces, al usar el análisis amortizado, podríamos probar que el esquema de la tabla dinámica tiene un tiempo de inserción O (1), que es un gran resultado utilizado en el hashing. Además, el concepto de tabla dinámica se usa en vectores en C++ y 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 caro.
2) El análisis amortizado anterior se realizó para el ejemplo de array dinámica que se denomina método agregado . Hay dos formas más poderosas de hacer un análisis Amortizado llamado Método de Contabilidady método potencial . Discutiremos los otros dos métodos en publicaciones separadas.
3) El análisis amortizado no involucra probabilidad. También hay otra noción diferente del tiempo de ejecución del caso promedio donde 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 tiempo de ejecución del peor de los casos. Estos algoritmos se analizan mediante análisis aleatorio. Ejemplos de estos algoritmos son Clasificación rápida aleatoria, Selección rápida y Hashing. Pronto cubriremos el análisis aleatorio en una publicación diferente.
Análisis amortizado de inserción en Red-Black Tree
Discutamos el análisis amortizado de las operaciones del árbol rojo-negro (inserción) utilizando el método potencial.
Para realizar el análisis amortizado de la operación de Inserción del Árbol Rojo-Negro, usamos el método del Potencial (o del Físico). Para el método potencial, definimos una función potencial 
que asigna una estructura de datos a un valor real no negativo. Una operación puede resultar en un cambio de este potencial.
Definamos la función de potencial de la siguiente manera:
donde n es un Node de Red-Black Tree
Función potencial = 
sobre todos los Nodes del árbol rojo negro.
Además, definimos el tiempo amortizado de una operación como:
Tiempo amortizado = c + 
(h)
(h)= (h’) – (h)
where h and h’ are the states of the Red-Black Tree before and after the operation respectively
c is the actual cost of the operation
El cambio de potencial debe ser positivo para operaciones de bajo costo y negativo para operaciones de alto costo.
Se inserta un nuevo Node en una hoja de un árbol rojo-negro. Tenemos las hojas de un árbol rojo-negro de cualquiera de los siguientes tipos:
Las inserciones y su análisis amortizado se pueden representar como:
(1)
Esta inserción se realiza volviendo a colorear primero al padre y al otro hermano (rojo). Luego, el abuelo y el tío de ese Node hoja se consideran para volver a colorear, lo que lleva a que el costo amortizado sea -1 (cuando el abuelo del Node hoja es rojo), -2 (cuando el tío de la hoja es negro y el abuelo es negro) o +1 (cuando el tío de la hoja es rojo y el abuelo es negro). La inserción se puede mostrar como:
(2)
En esta inserción, el nudo se inserta sin ningún cambio ya que la profundidad negra de las hojas permanece igual. Este es el caso cuando la hoja puede tener un hermano negro o no tiene ningún hermano (ya que consideramos que el color del Node nulo es negro).
Entonces, el costo amortizado de esta inserción es 0 .
(3)
En esta inserción, no podemos volver a colorear el Node hoja, su padre y el hermano de modo que la profundidad del negro permanezca igual que antes. Entonces, necesitamos realizar una rotación de izquierda a izquierda.
Después de la rotación, no hay cambios cuando el abuelo de g (el Node insertado) es negro. Además, para el caso del abuelo rojo de g (el Node insertado), no tenemos ningún cambio. Entonces, la inserción se completa con costo amortizado = +2 . La inserción se ha representado a continuación:
Después de calcular estos costos amortizados particulares en el sitio de la hoja de un árbol rojo-negro, podemos discutir la naturaleza del costo total amortizado de inserción en un árbol rojo-negro. Dado que esto puede suceder, dos Nodes rojos pueden tener una relación padre-hijo hasta la raíz del árbol rojo-negro.
Entonces, en el caso extremo (o esquina), reducimos el número de Nodes negros con dos hijos rojos en 1, y aumentamos como máximo el número de Nodes negros sin hijos rojos en 1, dejando una pérdida neta de como máximo 1 a la función potencial. Dado que una unidad de potencial paga por cada operación, por lo tanto
(h) 
n
where n is the total number of nodes
Por lo tanto, el costo total amortizado de inserción en el Árbol Rojo-Negro es O(n) .
Para cualquier duda con respecto a las inserciones en un árbol rojo-negro, puede consultar Inserciones en un árbol rojo-negro .
Para más detalles, consulte:
Diseño y Análisis de Algoritmos .
Escriba comentarios si encuentra algo incorrecto o si desea compartir más información sobre el tema tratado anteriormente.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA