Amortized nedir?
- Algoritmalar kursu
- Uzman seviye
- Ders 1/41
- 4 dk
Bir dizi işlemin ortalama maliyetini öğrenirsin.
Amortized nedir?
Amortized analiz, bir işlem dizisindeki ortalama maliyeti inceler. Tek bir işlem pahalı olsa bile, dizinin geneli ucuz olabilir.
Dinamik dizi örneğinde çoğu ekleme O(1), ama kapasite dolunca O(n) kopyalama gerekir. Ortalama (amortized) maliyet O(1)'dir.
Dinamik dizi
Dinamik dizi, sabit kapasiteli bir diziye eklemeye devam eder; kapasite dolunca yeni, iki kat büyük bir diziye kopyalar. Öğrenciye bu davranışı gösteren basit bir fonksiyon yazdıracağız.
Başlangıçta boş bir dizi döndüren fonksiyon, sonraki adımların temelini oluşturur.
Uygulama init_array fonksiyonu
init_array() yaz. Boş bir dizi döndür. print(init_array()) ile yazdır.
Başlangıç kodu
def init_array():
# Boş dizi döndürÖrnek çözüm
def init_array():
# Boş dizi döndür
return []
print(init_array())Beklenen çıktı
[]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Dinamik dizide kapasite dolunca ne olur?
- Dizi silinir
- Kapasite iki katına çıkar Doğru cevap
- Hata verilir
- Eleman atılır
Açıklama: Kapasite iki katına çıkarılır ve elemanlar kopyalanır.
2 başlangıç dizisi
arr = ____arr = []Açıklama: [] doğru.
3 Amortized nedir: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
amortized |
Ortalama |
dynamic array |
Dinamik dizi |
doubling |
İki kat |
copy |
Kopyala |