Az amortizált analízis az átlagos költséget mérí műveletek sorozatán, még akkor is, ha az egyes műveletek időnként jóval többe kerülnek. Megmagyarázza, miért "O(1) amortizált" a dinamikus tömb append-je az esetleges O(n) átméretezések ellenére.
Ha egy dinamikus tömb megtelt, új tömböt allokál (általában ) és az összes elemet másolja — egy O(n) lépés. De mivel a kapacitás , a drága másolások exponenciálisan ritkábbá válnak.
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
| Művelet | Legrosszabb egy | Amortizált |
|---|---|---|
| append (megkétszerezés) | O(n) | O(1) |
Állandó mennyiséggel való növekedés minden beszúrásnál másolást váltana ki, O(n) amortizáltat adva. A multiplikatív növekedés az, ami szétszórja a költséget.
Az amortizált analízis méltányos, reális képet ad a teljesítményről — nélküle jogosan félnél, hogy minden append vagy hash-tábla beszúrás O(n).
Egy kulcsfontosságú tervezési szabályt is indokol: a kapacitást multiplikatívan növeld, amely dinamikus tömböket, hash-táblákat és string megépítőket alapoz meg mindenütt.