Amortizuota analizė matuoja vidutinę operacijos kainą per veiksmų seką, net kai atskiros operacijos kartais kainuoja daug daugiau. Ji paaiškina, kodėl dinaminio masyvo append yra "O(1) amortizuota" nepaisant kartais pasitaikančių O(n) persidalijiųjimo operacijų.
Kai dinaminis masyvs prisipildo, jis paskyrbia naują masyvą (paprastai ) ir kopijuoja visus elementus — O(n) žingsnį. Bet nes talpa , brangios kopijos tampa eksponentiškai retesnės.
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 | Blogiausias atskiras | Amortizuota |
|---|---|---|
| append (padvigubinimas) | O(n) | O(1) |
Augimas pastovia suma reikalautų kiekvieno įdėjimo metu kopijuoti, suteikiant O(n) amortizuotą. Daugybinis augimas yra tai, kas paskleista išlaidas.
Amortizuota analizė suteikia teisingą, realistinę veikimo nuotrauką — be jos klaidingai bijotumėte, kad kiekvienas append ar maišos lentelės įdėjimas yra O(n).
Ji taip pat pagrindžia pagrindinę projektavimo taisyklę: auginti talpą daugybiškai, kuri yra dinaminio masyvo, maišos lentelių ir eilučių darklentės pagrindas visur.