A Análise Amortizada é usada para algoritmos em que uma operação ocasional é muito lenta, mas a maioria das outras operações é mais rápida. Na Análise Amortizada, analisamos uma sequência de operações e garantimos um tempo médio do pior caso, que é menor do que o tempo do pior caso de uma determinada operação cara. 
As estruturas de dados de exemplo cujas operações são analisadas usando a Análise Amortizada são Tabelas de Hash, Conjuntos Disjuntos e Árvores Splay. 

Vamos considerar um exemplo de inserção de uma tabela de hash simples. Como decidimos o tamanho da mesa? Há uma compensação entre espaço e tempo. Se aumentarmos o tamanho da tabela hash, o tempo de pesquisa torna-se baixo, mas o espaço necessário torna-se alto. 

A solução para esse problema de compensação é usar Tabela Dinâmica (ou Arrayes) . A ideia é aumentar o tamanho da mesa sempre que ela ficar cheia. A seguir estão as etapas a serem seguidas quando a mesa ficar cheia. 
1) Alocar memória para uma mesa maior de tamanho, normalmente o dobro da mesa antiga. 
2) Copie o conteúdo da tabela antiga para a nova. 
3) Liberte a mesa antiga. 

Se a mesa tiver espaço disponível, simplesmente inserimos um novo item no espaço disponível. 

Qual é a complexidade de tempo de n inserções usando o esquema acima?  
Se usarmos uma análise simples, o pior caso de custo de uma inserção é O (n). Portanto, o custo do pior caso de n inserções é n * O (n) que é O (n ² ). Esta análise fornece um limite superior, mas não um limite superior estreito para n inserções, pois todas as inserções não levam Θ (n) tempo. 

Assim, usando a Análise Amortizada, pudemos provar que o esquema da Tabela Dinâmica tem tempo de inserção O (1), o que é um ótimo resultado usado no hashing. Além disso, o conceito de tabela dinâmica é usado em vetores em C++, ArrayList em Java . 

A seguir estão algumas notas importantes. 
1) O custo amortizado de uma sequência de operações pode ser visto como despesa de um assalariado. A despesa média mensal da pessoa é menor ou igual ao salário, mas a pessoa pode gastar mais dinheiro em um determinado mês comprando um carro ou algo assim. Em outros meses, ele economiza dinheiro para o mês caro. 

2) A Análise Amortizada acima feita para o exemplo de Array Dinâmica é chamada de Método de Agregação . Existem duas maneiras mais poderosas de fazer a análise amortizada, chamadas Método de contabilidade e Método potencial . Estaremos discutindo os outros dois métodos em postagens separadas. 

3) A análise amortizada não envolve probabilidade. Há também outra noção diferente de tempo de execução de caso médio, onde algoritmos usam randomização para torná-los mais rápidos e o tempo de execução esperado é mais rápido do que o tempo de execução de pior caso. Esses algoritmos são analisados ​​por meio de análise aleatória. Exemplos desses algoritmos são Classificação rápida aleatória, Seleção rápida e Hashing. Em breve estaremos cobrindo a análise aleatória em uma postagem diferente. 

Análise amortizada de inserção em Red-Black Tree 

Vamos discutir a Análise Amortizada de operações Red-Black Tree (Inserção) usando o Método do Potencial. 

Para realizar a análise amortizada da operação Red-Black Tree Insertion, usamos o método Potencial (ou Físico). Para método potencial, definimos uma função potencial  que mapeia uma estrutura de dados para um valor real não negativo. Uma operação pode resultar em uma alteração desse potencial. 

Vamos definir a função potencial  da seguinte maneira: 

(1)  

onde n é um nó da árvore vermelho-preto 

Função potencial  =  , sobre todos os nós da árvore vermelho-preto. 

Além disso, definimos o tempo amortizado de uma operação como: 

Tempo amortizado = c +  (h) 

(h) =  (h ') -  (h) 
onde h e h' são os estados da Árvore Vermelho-Preto antes e depois da operação, respectivamente 
c é o custo real da operação 

A mudança no potencial deve ser positiva para operações de baixo custo e negativa para operações de alto custo. 

Um novo nó é inserido em uma folha de uma árvore vermelho-preta. Temos as folhas de uma árvore vermelho-preta de qualquer um dos seguintes tipos: 
 

As inserções e suas análises amortizadas podem ser representadas como: 
(1) 

Esta inserção é realizada recolorindo primeiro o pai e o outro irmão (vermelho). Em seguida, o avô e o tio desse nó da folha são considerados para nova coloração, o que leva ao custo amortizado a ser -1 (quando o avô do nó da folha é vermelho), -2 (quando o tio da folha é preto e o avô é preto) ou +1 (quando o tio da folha é vermelho e o avô é preto). A inserção pode ser mostrada como: 
 

(2) 
 

Nesta inserção, o nó é inserido sem nenhuma alteração, pois a profundidade do preto das folhas permanece a mesma. Este é o caso quando a folha pode ter um irmão preto ou não ter nenhum irmão (visto que consideramos a cor da cor do nó nulo como preta). 

Portanto, o custo amortizado dessa inserção é 0 . 

(3) 
 

Nesta inserção, não podemos recolorir o nó folha, seu pai e o irmão de forma que a profundidade do preto permaneça a mesma de antes. Portanto, precisamos realizar uma rotação Esquerda-Esquerda. 

Após a rotação, não há alterações quando o avô de g (o nó inserido) é preto. Além disso, para o caso do Avô Vermelho de g (o nó inserido), não temos nenhuma alteração. Portanto, a inserção é concluída com custo amortizado = +2 . A inserção foi descrita abaixo: 
 

Depois de calcular esses custos amortizados específicos no local da folha de uma árvore vermelho-preta, podemos discutir a natureza do custo amortizado total de inserção em uma árvore vermelho-preta. Uma vez que isso pode acontecer, dois nós vermelhos podem ter uma relação pai-filho até a raiz da árvore vermelho-preto. 

Portanto, no caso extremo (ou canto), reduzimos o número de nós pretos com dois filhos vermelhos em 1 e no máximo aumentamos o número de nós pretos sem filhos vermelhos em 1, deixando uma perda líquida de no máximo 1 para o potencial função. Uma vez que uma unidade de potencial paga por cada operação, portanto 

(h)  n 
onde n é o número total de nós 

Assim, o custo total amortizado de inserção na Red-Black Tree é O (n) . 

Para qualquer dúvida a respeito de inserções na árvore vermelho-preto, você pode consultar Inserções na árvore Vermelho-Preto . 

Fontes:  
Berkeley Lecture 35: Amortized Analysis 
MIT Lecture 13: Amortized Algorithms, Table Doubling, Potential Method 
http://www.cs.cornell.edu/courses/cs3110/2011sp/lectures/lec20-amortized/amortized.htm 
http: / /web.iitd.ac.in/~csz188551/COL106_2019/ 

Escreva comentários se encontrar algo incorreto ou se quiser compartilhar mais informações sobre o tópico discutido acima.