Dinamik dizi örneği
- Algoritmalar kursu
- Uzman seviye
- Ders 3/41
- 4 dk
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.
Başlangıç kodu
def total_cost(n):
# n ekleme için toplam maliyeti hesaplaÖrnek çözüm
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))Beklenen çıktı
7
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Dinamik dizi örneği: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
write |
1 |
copy |
size |
capacity |
İki kat |
size |
Mevcut |
2 total_cost(4) kaç döner?
- 4
- 6
- 8
- 7 Doğru cevap
Açıklama: 1+2+3+1=7 (1. push 1, 2. push 2, 3. push 3, 4. push 1).
3 kapasite güncelleme
capacity ____ 2capacity *= 2Açıklama: *= doğru.