Amorterad analys mäter genomsnittskostnaden per operation över en sekvens, även när enskilda operationer ibland kostar mycket mer. Det förklarar varför append på ett dynamiskt array är "O(1) amorterad" trots ibland O(n) omstorlekar.
När ett dynamiskt array blir fullt allokeras en ny array (oftast ) och alla element kopieras — ett O(n) steg. Men eftersom kapaciteten blir dyra kopieringar exponentiellt mer sällsynta.
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
| Operation | Värsta fall | Amorterad |
|---|---|---|
| append (fördubbling) | O(n) | O(1) |
Omstorlek med en konstant mängd skulle göra att varje insert utlöser en kopia, vilket ger O(n) amorterad. Multiplikativ tillväxt är det som sprider kostnaden.
Amorterad analys ger en rättvis, realistisk bild av prestanda — utan den skulle du felaktigt frukta att varje append eller hash-table insert är O(n).
Det justifierar också en nyckeldesignregel: multiplikativ tillväxt av kapacitet, som ligger till grund för dynamiska arrays, hashtabeller och string builders överallt.