Aggregate yöntem
- Algoritmalar kursu
- Uzman seviye
- Ders 2/41
- 4 dk
Toplam maliyeti sayıp ortalamayı öğrenirsin.
Aggregate yöntem
Aggregate yöntem, n işlem için toplam maliyeti hesaplar ve n'ye bölerek amortized maliyeti bulur. Dinamik dizi için toplam maliyet O(3n)'dir; amortized O(1).
Bu yöntem, en basit amortized analiz tekniğidir. Tüm işlemlerin toplam maliyeti hesaplanır.
Append işlemi
append metodu, diziye yeni eleman ekler. Çoğu zaman bu işlem O(1)'dir; yalnızca kapasite doluysa O(n) olur.
Yine de amortized maliyet O(1)'dir çünkü pahalı kopyalama nadiren gerçekleşir. Aggregate yöntem bunu kanıtlar.
Uygulama append_dyn fonksiyonu
append_dyn(arr, item) yaz. arr'ye item ekle, yeni diziyi döndür. print(append_dyn([1, 2], 3)) ile [1, 2, 3] yazdır.
Başlangıç kodu
def append_dyn(arr, item):
# Diziye eleman ekleÖrnek çözüm
def append_dyn(arr, item):
# Diziye eleman ekle
arr.append(item)
return arr
print(append_dyn([1, 2], 3))Beklenen çıktı
[1, 2, 3]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 ortalama hesabı
amortized = total_cost ____ namortized = total_cost / nAçıklama: / doğru.
2 Append çoğu zaman hangi karmaşıklığa sahiptir?
- O(n²)
- O(n)
- O(1) Doğru cevap
- O(log n)
Açıklama: Append çoğu zaman O(1)'dir.
3 Aggregate yöntem: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
append |
Ekle |
total |
Toplam |
amortized |
Ortalama |
O(1) |
Sabit |