Amortized analysis mengukur biaya rata-rata per operasi selama urutan, bahkan ketika operasi individual sesekali jauh lebih mahal. Ini menjelaskan mengapa append dari dynamic array adalah "O(1) amortized" meskipun ada resize O(n) yang sesekali.
Ketika dynamic array penuh, ia mengalokasikan array baru (biasanya ) dan menyalin semua elemen — langkah O(n). Tapi karena kapasitas , penyalinan yang mahal menjadi semakin jarang secara eksponensial.
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
| Operasi | Kasus terburuk | Amortized |
|---|---|---|
| append (penggandaan) | O(n) | O(1) |
Bertumbuh dengan jumlah konstan akan memicu penyalinan pada setiap sisipan, memberikan O(n) amortized. Pertumbuhan multiplikatif adalah yang menyebarkan biaya.
Amortized analysis memberikan gambaran performa yang adil dan realistis — tanpanya, Anda akan salah takut bahwa setiap append atau penyisipan hash-tabel adalah O(n).
Ini juga membenarkan aturan desain kunci: tumbuhkan kapasitas secara multiplikatif, yang melandasi dynamic array, hash table, dan string builder di mana-mana.