Geamortiseerde analyse meet de gemiddelde kosten per operatie over een reeks, zelfs als individuele operaties soms veel duurder zijn. Het verklaart waarom een dynamische array's append "O(1) geamortiseerd" is ondanks af en toe O(n) resizes.
Wanneer een dynamische array vol raakt, wijst deze een nieuwe array toe (meestal ) en kopieert alle elementen — een O(n) stap. Maar omdat capaciteit , worden dure kopieën exponentieel zeldzamer.
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
| Operatie | Slechtste enkel | Geamortiseerd |
|---|---|---|
| append (verdubbelen) | O(n) | O(1) |
Groeien met een constant bedrag zou elke invoeging een kopie triggeren, wat O(n) geamortiseerd geeft. Multiplicatieve groei is wat de kosten verspreidt.
Geamortiseerde analyse geeft een eerlijk, realistisch beeld van prestaties — zonder het zou je terecht vrezen dat elke append of hash-table insert O(n) is.
Het rechtvaardigt ook een belangrijke ontwerpregel: capaciteit multiplicatief vergroten, wat ten grondslag ligt aan dynamische arrays, hash-tabellen en string builders overal.