📊 Análise Amortizada

Em alguns problemas, olhar para uma operação isolada não é suficiente.

E quando uma operação às vezes é cara, mas quase sempre é barata?

É exatamente aí que entra a análise amortizada.

A ideia central

Na análise amortizada, não perguntamos apenas:

"quanto custa esta operação específica?"

Perguntamos:

"quanto custa, em média, uma sequência grande dessas operações?"

O objetivo é entender o custo distribuído ao longo do tempo.

Uma operação pode ser cara de vez em quando sem tornar a estrutura ineficiente como um todo.

Um exemplo intuitivo: array dinâmico

Imagine um array que começa com capacidade para 4 elementos. Inserir no final costuma ser simples:

• coloca o elemento na próxima posição livre
• custo baixo

Mas o que acontece quando o array enche?

Nesse momento, precisamos:

1. criar um array maior
2. copiar todos os elementos antigos
3. inserir o novo elemento

Essa inserção específica é bem mais cara do que as anteriores.

O custo parece ruim isoladamente

Se a capacidade acabou e havia n elementos, essa operação pode custar algo como n, porque precisamos copiar tudo.

Olhando só para essa inserção, poderíamos pensar:

"então inserir no final é O(n)?"

Mas isso seria uma conclusão incompleta.

Essa cópia não acontece toda hora. Ela acontece apenas em momentos específicos.

O que acontece ao longo de muitas inserções?

Suponha que a capacidade dobre sempre que o array enche.

As capacidades podem evoluir assim:

• 1
• 2
• 4
• 8
• 16

As cópias acontecem justamente nesses saltos.

Se somarmos o custo dessas cópias, temos algo como:

1 + 2 + 4 + 8 + ... + n

Essa sequência cresce dobrando a cada etapa.

E existe um resultado importante:

1 + 2 + 4 + 8 + ... + n ~= 2n

Ou seja, mesmo somando todas as realocações, o custo total continua proporcional a n.

Se inserirmos muitos elementos, teremos várias inserções baratas e poucas inserções caras.

Quando somamos tudo, o custo total continua bem controlado.

Intuição do custo amortizado

Vamos imaginar uma sequência de inserções:

• várias custam 1
• algumas poucas custam mais porque disparam realocação e cópia

Mesmo com esses picos, o custo total de n inserções continua proporcional a n.

Por isso, dizemos que a inserção no final de um array dinâmico tem custo amortizado:

O(1)

Isso não significa que toda inserção custa constante. Significa que, ao longo de muitas inserções, o custo médio por operação fica constante.

Operação individual vs. custo amortizado

Essa distinção é essencial:

• Custo individual: quanto uma execução específica custa
• Custo amortizado: quanto custa, em média, cada operação dentro de uma sequência longa

No array dinâmico:

• uma inserção específica pode custar O(n)
• mas o custo amortizado por inserção continua sendo O(1)

Por que isso importa?

Sem análise amortizada, algumas estruturas pareceriam piores do que realmente são.

Ela é útil porque permite responder:

• uma operação cara é frequente ou rara?
• esse pico de custo compromete a estrutura?
• o comportamento global continua eficiente?

Onde isso aparece?

Análise amortizada aparece bastante em estruturas de dados e operações que:

• fazem realocação ocasional
• reorganizam dados de tempos em tempos
• pagam um custo maior agora para baratear operações futuras

Exemplos comuns:

• inserção em array dinâmico
• algumas operações em pilhas e filas implementadas com estruturas auxiliares
• certas estruturas mais avançadas que reorganizam seu conteúdo periodicamente

Uma analogia útil

Pense em abastecer um reservatório.

Na maior parte do tempo, você apenas usa a água disponível. De vez em quando, precisa reabastecer tudo de uma vez, o que custa mais.

Se analisarmos só o momento do reabastecimento, parece caro. Mas, distribuindo esse custo ao longo do uso, o sistema pode continuar sendo eficiente.

O que a análise amortizada não é

Ela não é exatamente:

• pior caso
• melhor caso
• caso médio tradicional

Ela olha para uma sequência de operações, e não apenas para uma entrada isolada.

Isso é o que diferencia esse tipo de análise de leituras focadas apenas em uma única execução.

Resumo

• A análise amortizada estuda o custo de uma sequência de operações.
• Uma operação individual pode ser cara sem prejudicar o custo global.
• Em arrays dinâmicos, algumas inserções exigem cópia, mas a maioria é barata.
• Por isso, a inserção no final pode ter custo amortizado O(1).

Esse tipo de análise aparece bastante quando operações ocasionalmente caras ficam distribuídas ao longo de muitas execuções.