Análise amortizada
Por que 'append' é O(1) mesmo custando O(n) de vez em quando — e as três formas de provar isso.
xs.append(x) é O(1). Só que de vez em quando ele copia a lista inteira, o que é O(n). As duas frases são verdadeiras, e a análise amortizada é o que as concilia.
A pergunta certa não é quanto custa esta operação, e sim quanto custam n operações, divididas por n. É a diferença entre a conta do mês e a conta do café.
O que acontece por dentro#
Um cluster guarda um bloco de memória com espaço sobrando. Quando o espaço acaba, ele aloca um bloco maior — tipicamente o dobro — e copia o que havia. Essa cópia é a operação cara.
capacidade: 4 8 16 32
append: ···· ····**** ····****········ …
↑ ↑ ↑
copia 4 copia 8 copia 16A cópia acontece cada vez mais raramente, e é exatamente por isso que ela some na média.
A prova pela agregação#
Some o custo de n appends. As cópias acontecem em 1, 2, 4, 8, …, até n — uma série geométrica:
1 + 2 + 4 + 8 + … + n < 2nO total das cópias é menor que `2n`, e somado aos n appends dá menos de 3n. Dividido por n: uma constante. Cada append custa O(1) amortizado.
A prova pela medição#
A conta acima é verificável sem confiar em ninguém: se o total de n appends é linear, dobrar n tem de dobrar o tempo. Dobre quatro vezes e olhe a razão.
adopt Arcane.Time as T
action tempo_de_n_appends(n):
inicio := T.monotonic()
xs := []
cycle i from 1 to n:
xs.append(i)
yield (T.monotonic() - inicio) * 1000
anterior := 0.0
cycle n in [100000, 200000, 400000, 800000]:
ms := tempo_de_n_appends(n)
razao := "—" given anterior is 0.0 otherwise $"{round(ms / anterior, 2)}x"
out $"{str(n).pad_start(7)} appends {str(round(ms, 1)).pad_start(7)} ms {razao}"
anterior := ms 100000 appends 88.2 ms —
200000 appends 178.2 ms 2.02x
400000 appends 360.1 ms 2.02x
800000 appends 724.4 ms 2.01x2,02x três vezes seguidas. Se cada append fosse O(n), dobrar n daria 4x; se as cópias não amortizassem, a razão subiria a cada linha. Ela não sobe.
As outras duas provas#
A agregação responde "quanto custa o total". As outras duas respondem "por que nunca falta", e são o que se usa quando a estrutura é mais complicada que uma lista:
| Método | A ideia | Aplicado ao append |
|---|---|---|
| agregação | some tudo e divida por n | menos de 3n para n appends |
| contábil | cobre a mais em cada operação barata e guarde o crédito | cada append paga 3: um por si, dois guardados para a cópia futura |
| potencial | defina uma função Φ do estado; o custo amortizado é o real mais a variação de Φ | Φ = 2 × (itens além da metade da capacidade) |
As três dão o mesmo resultado. A contábil é a mais fácil de explicar: quando o bloco de capacidade k enche, os k itens copiados já pagaram, cada um, os dois créditos que a cópia consome.
Amortizado não é o mesmo que médio#
| Sobre o quê | Quem garante | |
|---|---|---|
| caso médio | uma distribuição de entradas | a estatística — pode dar azar |
| amortizado | uma sequência de operações | a álgebra — não tem azar |
O quicksort é O(n log n) no caso médio e O(n²) no pior: uma entrada infeliz custa caro. O append é O(1) amortizado: não existe sequência de appends que fuja disso. Ver melhor, médio e pior.
Onde isso muda a decisão#
- Construir uma lista com `append` num laço é linear, e não quadrático. A alternativa "esperta" —
saida := [...saida, x]— é quadrática, porque copia a cada volta. - Num sistema de tempo real, o amortizado não basta. A cópia acontece de verdade, e naquela volta o prazo estoura. Ali se pré-aloca.
- Um vault tem a mesma história, com um detalhe a mais: ele também cresce por realocação, e uma colisão ruim de chaves degrada a busca.
// linear: cada append é O(1) amortizado
saida := []
cycle x in fonte:
saida.append(x)
// quadrático: cada volta copia a lista inteira
saida := []
cycle x in fonte:
saida := [...saida, x]O dataforge big-o acusa o segundo — é o padrão 4 da lista de armadilhas.