Análise amortizada

Algumas operações são caras de vez em quando e baratas quase sempre. A análise amortizada mede o custo médio por operação no pior caso de uma sequência inteira, sem nenhuma probabilidade envolvida.

Array dinâmico (list do Python, ArrayList, Vec)

Quando o array enche, alocamos o dobro e copiamos tudo. Uma cópia custa O(n), mas quanto custam n inserções no total?

Cópias: 1 + 2 + 4 + … + n/2 + n  <  2n
Custo total de n appends  ≤  n + 2n  =  3n  ⇒  O(1) amortizado

Se o array crescesse em +k posições fixas em vez de dobrar, as cópias somariam k + 2k + … ≈ n²/(2k): O(n) amortizado por append. O crescimento geométrico é o que faz funcionar.

import sys
xs = []
ultimo = sys.getsizeof(xs)
for i in range(64):
    xs.append(i)
    agora = sys.getsizeof(xs)
    if agora != ultimo:
        print(f"len={len(xs):3}  bytes={agora}")   # realocações cada vez mais espaçadas
        ultimo = agora