Dinamik dizi örneği

Dinamik dizinin çift maliyetli ama amortized O(1) olduğunu öğrenirsin.

Dinamik dizi simülasyonu

n eleman eklemenin toplam maliyetini simüle edelim. Her ekleme bir yazma işlemidir; kapasite dolunca ayrıca kopyalama yapılır.

Bu simülasyon, amortized analizin pratik karşılığını gösterir. Toplam maliyet, teorik üst sınıra yakın çıkar.

Maliyet formülü

n eleman için toplam maliyet: n yazma + kopyalama maliyetleri. Kopyalama, 1+2+4+...+2^k şeklinde büyür; toplam n'den az olur. Sonuç: O(3n) ≈ 2n.

Bu, amortized maliyetin O(1) olduğunun pratik kanıtıdır. Her ekleme ortalama sabit sürede yapılır.

Uygulama total_cost fonksiyonu

total_cost(n) yaz. n ekleme simüle et; her ekleme 1 yazma, kapasite dolunca ek kopyalama. Toplam maliyeti döndür. print(total_cost(4)) ile 7 yazdır.

Örnek çözümü göster

def total_cost(n):
    # n ekleme için toplam maliyeti hesapla
    cost = 0
    capacity = 1
    size = 0
    for i in range(n):
        if size == capacity:
            cost += size
            capacity *= 2
        cost += 1
        size += 1
    return cost
print(total_cost(4))

Kendini test et

Dinamik dizi örneği: kavramları eşleştir

write

1
copy

size
capacity

İki kat
size

Mevcut
total_cost(4) kaç döner?
- 4
- 6
- 8
- 7
Cevabı göster

7 — 1+2+3+1=7 (1. push 1, 2. push 2, 3. push 3, 4. push 1).
kapasite güncelleme
```
capacity ____ 2
```
Cevabı göster
```
capacity *= 2
```

Sıradaki ders: Özet - Amortized

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler