Amortized analiz, bireysel işlemler bazen çok daha pahalı olsa bile, bir dizi boyunca operasyon başına ortalama maliyeti ölçer. Dinamik bir dizinin append işleminin neden "O(1) amortized" olduğunu açıklar, ara sıra O(n) yeniden boyutlandırmalara rağmen.
Dinamik bir dizi dolduğunda, yeni bir dizi (genellikle ) ayırır ve tüm öğeleri kopyalar — O(n) adımı. Ancak kapasite çıktığı için, pahalı kopyalama katlanarak nadirleşir.
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
| İşlem | En kötü durum | Amortized |
|---|---|---|
| append (ikiye katlamak) | O(n) | O(1) |
Sabit bir miktarla büyümek, her insert işlemini bir kopyayı tetikleyecek şekilde yapar ve O(n) amortized'e neden olur. Çarpımsal büyüme, maliyeti yayıltan şeydir.
Amortized analiz, adil ve gerçekçi bir performans resmi sunar — olmazsa, her append veya hash tablosu insert işleminin O(n) olduğundan haksız yere korka sınız.
Ayrıca bir tasarım kuralını haklı çıkarır: kapasitenin çarpımsal büyümesi, bu dinamik diziler, hash tabloları ve her yerde string builders'ın temelini oluşturur.