Amortized analysis mengukur purata kos setiap operasi sepanjang jujukan, walaupun operasi individu kadangkala berkos jauh lebih tinggi. Ia menerangkan mengapa append array dinamik ialah "O(1) ter-amortize" walaupun terdapat resize O(n) sekali-sekala.
Apabila array dinamik penuh, ia memperuntukkan array baharu (biasanya ) dan menyalin semua elemen — satu langkah O(n). Tetapi oleh sebab kapasiti , salinan yang mahal menjadi semakin jarang secara eksponen.
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 | Tunggal terburuk | Ter-amortize |
|---|---|---|
| append (gandaan) | O(n) | O(1) |
Berkembang dengan amaun tetap akan menyebabkan setiap insert mencetuskan salinan, memberikan O(n) ter-amortize. Pertumbuhan secara pendaraban itulah yang menyebarkan kos.
Amortized analysis memberikan gambaran prestasi yang adil dan realistik — tanpanya, anda akan tersilap takut bahawa setiap append atau insert hash table ialah O(n).
Ia juga mewajarkan satu peraturan reka bentuk utama: kembangkan kapasiti secara pendaraban, yang mendasari array dinamik, hash table, dan string builder di mana-mana sahaja.