Fibonacci memoization
- Algoritmalar kursu
- İleri seviye
- Ders 2/56
- 4 dk
Recursive Fibonacci'yi memoization ile hızlandırmayı öğrenirsin.
Fibonacci memoization
Recursive Fibonacci'yi memoization ile hızlandır: her n için sonucu bir sözlükte sakla.
İlk çağrıda hesapla ve sakla; sonraki çağrılarda saklanan değeri döndür.
Bu küçük değişiklik, fibonacci'yi Θ(2^n)'den Θ(n)'ye indirir; büyük fark yaratır.
Sözlük kontrolü
Önce n'nin önbellekte olup olmadığını kontrol et. Varsa direkt döndür; yoksa hesapla ve sakla.
Bu, her alt problemin yalnızca bir kez çözülmesini sağlar.
Önbellek kontrolü, memoization'ın kalbidir; doğru uygulanmalıdır.
Uygulama Fibonacci memo
fib_memo(n, memo) yaz. Recursive Fibonacci + memoization. print(fib_memo(10, {})) ile 55 yazdır.
Başlangıç kodu
def fib_memo(n, memo):
# Fibonacci memoÖrnek çözüm
def fib_memo(n, memo):
# Fibonacci memo
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo(n - 1, memo) + fib_memo(n - 2, memo)
return memo[n]
print(fib_memo(10, {}))Beklenen çıktı
55
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Önbellek kontrolü
if n in ____:if n in memo:Açıklama: memo doğru.
2 Fibonacci memoization: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
memo |
Önbellek |
dict |
Sözlük |
n |
Parametre |
return |
Döndür |
3 Fibonacci memoization karmaşıklığı nedir?
- Θ(log n)
- Θ(2^n)
- Θ(n^2)
- Θ(n) Doğru cevap
Açıklama: Θ(n).