Análise amortizada mede o custo médio por operação em uma sequência, mesmo quando operações individuais ocasionalmente custam muito mais. Explica por que append de um array dinâmico é "O(1) amortizado" apesar de redimensionamentos ocasionais O(n).
Quando um array dinâmico fica cheio, aloca um novo array (geralmente ) e copia todos os elementos — uma etapa O(n). Mas porque a capacidade , cópias caras se tornam exponencialmente mais raras.
Appending into a doubling array (cap shown):
ops: 1 2 3 4 5 6 7 8 9
cap: 1 2 4 4 8 8 8 8 16
copy: * * * * * <- copies at 1,2,4,8,16...
To insert n elements, total copy work =
1 + 2 + 4 + ... + n ≈ 2n (geometric series)
Total cost for n inserts = O(n)
Amortized cost per insert = O(n)/n = O(1)
arr = []
for i in range(1_000_000):
arr.append(i) # almost always O(1); rarely O(n) during a resize
| Operação | Pior caso único | Amortizado |
|---|---|---|
| append (duplicação) | O(n) | O(1) |
Crescer por um valor constante faria cada inserção ativar uma cópia, dando O(n) amortizado. O crescimento multiplicativo é o que distribui o custo.
Análise amortizada oferece uma visão justa e realista do desempenho — sem ela, você equivocadamente temeria que cada append ou inserção em hash-table fosse O(n).
Também justifica uma regra de design fundamental: aumente a capacidade multiplicativamente, que fundamenta arrays dinâmicos, tabelas hash e construtores de strings em toda parte.