Analiza amortizuese mat koston mesatare për operacion gjatë një sekuence, edhe kur operacionet individuale kohë pas kohe kushtojnë shumë më tepër. Ajo shpjegon pse append i një grupi dinamik është "O(1) amortizuar" përkundër ndryshimeve të rastësishme O(n).
Kur një grup dinamik mbushet, ai alokuon një grup të ri (zakonisht ) dhe kopjon të gjithë elementët — një hap O(n). Por sepse kapaciteti , kopjimet e shtrenjta bëhen eksponencialisht më të rralla.
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
| Operacion | Më i keqi | Amortizuar |
|---|---|---|
| append (dyfishim) | O(n) | O(1) |
Rritja për një sasi konstante do të bënte që secili insert të shkaktojë një kopje, duke dhënë O(n) amortizuar. Rritja multiplikative është ajo që përhapon koston.
Analiza amortizuese jep një pamje të drejtë, realiste të performancës — pa të, do të frikesoheshit gabimisht se çdo append ose insert në tabelën hash është O(n).
Ajo gjithashtu justifikon një rregull kyç të projektimit: rritja multiplikative e kapacitetit, e cila është baza e grupeve dinamike, tabelave hash dhe string builderve kudo.