Amortize, beklenen ve deneysel maliyet

Amortize analiz, bir işlem dizisinin toplam maliyetini işlemlere dağıtır; olasılık gerektirmez. Kapasitesini iki katına çıkaran dinamik dizide bazı append işlemleri n elemanı kopyalar fakat n eklemenin toplam kopyalama işi geometrik toplamla O(n) olur. Bir append'in en kötü maliyeti O(n), amortize maliyeti O(1)'dir.

Aggregate yöntem toplamı doğrudan sayar; accounting ucuz işlemlere kredi yükler; potential yöntemi veri yapısında depolanmış işi Φ ile temsil eder. Beklenen analiz ise bir olasılık dağılımı kullanır: rastgele pivotlu quicksort'un beklentisi algoritmanın rastgeleliğine göredir, “tipik kullanıcı verisi” iddiası değildir.

Benchmark'ta girdi dağılımı, warm-up, tekrar sayısı, median/p95, bellek ve çalışma ortamı kaydedilir. Aynı asimptotik sınıfta cache davranışı ve sabitler belirleyici olabilir. Amortize O(1), gecikme hassas bir serviste her isteğin kısa süreceği garantisini vermez; tek büyük yeniden boyutlandırma gecikmesi önemlidir.

Dinamik dizide potansiyel nasıl birikir?

Kapasite dolunca ikiye katlanan dizi düşün. n eklemede taşınan eski elemanlar 1+2+4+… biçimindedir. Son terim n'den küçüktür ve geometrik toplam 2n'den küçüktür. Yeni elemanların n yazımıyla toplam doğrusal kalır. Tek pahalı append Θ(n) olabilir; bütün sequence başına ortalama amortize Θ(1)'dir. Bu, rastgele input ortalaması değildir.

Accounting yönteminde her append'e birkaç kredi yükle: bir kredi mevcut yazmaya, kalan krediler ilerideki resize'a ayrılır. Potential yöntemi aynı fikri Φ(state) ile formelleştirir. Amortize maliyet gerçek maliyet + ΔΦ'dir. Potansiyelin başlangıçta kontrollü ve bütün sequence boyunca aşağıdan sınırlı olması gerekir.

Silmede kapasite yarıya küçültülürse eşik önemlidir. Yarı dolulukta büyüt/küçült yapmak peş peşe insert/delete ile thrashing oluşturabilir. Örneğin büyütme doluyken, küçültme dörtte bir doluyken yapılır; arada yeniden maliyet ödeyecek kadar ucuz işlem birikir. Bu hysteresis tasarımını latency hedefiyle de değerlendir: amortize guarantee tek bir kullanıcı isteğinin hızlı olacağını garanti etmez.

Temel: 8 ekleme için resize anlarını yaz. Orta: 1.5 büyüme factor'ında geometrik toplamı çıkar. İleri: Her işlem için sıkı gecikme gerekiyorsa incremental migration tasarla; eski/yeni buffer birlikteyken lookup invariantını belirt.

def copied_items(n):
    capacity, size, copied = 1, 0, 0
    for _ in range(n):
        if size == capacity:
            copied += size
            capacity *= 2
        size += 1
    return copied
assert copied_items(16) == 15