Amortizirana analiza meri povprečno ceno na operacijo v zaporedju, tudi kadar posamezne operacije včasih stanejo veliko več. Pojasnjuje, zakaj je append dinamičnega polja "O(1) amortiziran" kljub občasnim O(n) spremembam velikosti.
Kadar se dinamično polje napolni, dodeli novo polje (običajno ) in kopira vse elemente — O(n) korak. Ker se kapaciteta , postanejo dragi kopiranja eksponentno redkejši.
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
| Operacija | Najslabši primer | Amortiziran |
|---|---|---|
| append (podvojitev) | O(n) | O(1) |
Rastenje za konstanten znesek bi povzročilo, da bi vsak vnos sprožil kopiranje, kar bi dalo O(n) amortiziran rezultat. Multiplikativna rast je tista, ki razprši stroške.
Amortizirana analiza daje pošteno, realistično sliko zmogljivosti — brez nje bi se nepravilno bali, da je vsak append ali vstavljanje v hash tabelo O(n).
Prav tako upravičuje ključno pravilo oblikovanja: multiplikativna rast kapacitete, ki je osnova dinamičnih polj, hash tabel in string builderjev povsod.