L'analisi ammortizzata misura il costo medio per operazione su una sequenza, anche quando le singole operazioni occasionalmente costano molto di più. Spiega perché l'append di un array dinamico è "O(1) ammortizzato" nonostante i ridimensionamenti occasionali O(n).
Quando un array dinamico si riempie, alloca un nuovo array (solitamente ) e copia tutti gli elementi — un passaggio O(n). Ma poiché la capacità , le copie costose diventano esponenzialmente più rare.
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
| Operazione | Peggiore singola | Ammortizzata |
|---|---|---|
| append (raddoppiamento) | O(n) | O(1) |
L'analisi ammortizzata fornisce un'immagine giusta e realistica delle prestazioni — senza di essa, avresti ingiustificati timori che ogni append o inserimento in hash-table sia O(n).
Giustifica inoltre una regola chiave di progettazione: aumentare la capacità moltiplicativamente, che è alla base degli array dinamici, delle hash table e dei string builder ovunque.