Meydan okuma 1
- Algoritmalar kursu
- Uzman seviye
- Ders 37/41
- 4 dk
Amortized maliyeti yazdırırsın.
Meydan okuma 1 - Amortized
Birinci meydan okuma, amortized analiz konusunu yoklar. Dinamik dizi append işleminin ortalama maliyeti O(1)'dir; bunu ikiye katlama sayısını sayarak gösteririz.
n append sırasında dizi kapasitesi 1, 2, 4, 8, ... şeklinde ikiye katlanır. Toplam ikiye katlama sayısı floor(log2(n))'dir.
Şimdi bu sayıyı hesaplayan bir fonksiyon yazacaksın.
Uygulama count_doublings fonksiyonu
count_doublings(n) yaz. n append sırasında kaç kez ikiye katlandığını döndür. print(count_doublings(8)) ile 3 yazdır.
Başlangıç kodu
def count_doublings(n):
# n append sırasında ikiye katlama sayısıÖrnek çözüm
def count_doublings(n):
# n append sırasında ikiye katlama sayısı
count = 0
size = 1
last = 0
for i in range(n):
if last == size:
size *= 2
count += 1
last += 1
return count
print(count_doublings(8))Beklenen çıktı
3
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Dinamik dizi append'in amortized maliyeti?
- O(1) Doğru cevap
- O(log n)
- O(n)
- O(n²)
Açıklama: Dinamik dizi append'in amortized maliyeti O(1)'dir.
2 ikiye katlama
Soru
if last == size:
size *= ____
count += 1
Cevap
if last == size:
size *= 2
count += 1Açıklama: Kapasite ikiyle çarpılır.
3 Amortized kavramlar
| Kavram | Anlamı |
|---|---|
amortized |
Ortalama maliyet |
ikiye katlama |
Kapasite artışı |
O(1) |
Append başına |
floor(log2(n)) |
Kat sayısı |