Memoization nedir?
- Algoritmalar kursu
- İleri seviye
- Ders 1/56
- 4 dk
Hesaplanan alt sonuçları saklayarak tekrar hesabı önlemeyi öğrenirsin.
Memoization nedir?
Memoization, hesaplanan alt sonuçları bir önbellekte saklayarak tekrar hesabı önler.
Recursive Fibonacci'de aynı alt problem defalarca çözülür; memoization bunu önler.
Memoization, üstel karmaşıklığı polinomsala indirir; fibonacci Θ(n) olur.
Önbellek
Önbellek, genelde bir sözlük (dict) ya da dizidir. Anahtar alt problemin parametresidir.
İlk hesapta sonuç önbelleğe yazılır; sonraki çağrılarda önbellekten okunur.
Bu sayede aynı alt problem yalnızca bir kez çözülür; toplam süre düşer.
Uygulama Fibonacci karşılaştırma
fib_naive(n) yaz. Recursive naive Fibonacci. print(fib_naive(10)) ile 55 yazdır.
Başlangıç kodu
def fib_naive(n):
# Naive FibonacciÖrnek çözüm
def fib_naive(n):
# Naive Fibonacci
if n <= 1:
return n
return fib_naive(n - 1) + fib_naive(n - 2)
print(fib_naive(10))Beklenen çıktı
55
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Memoization neyi önler?
- Tekrar hesabı Doğru cevap
- Bellek kullanımını
- Recursion
- Döngüleri
Açıklama: Tekrar hesabı.
2 Önbellek yapısı
memo = ____memo = {}Açıklama: {} doğru.
3 Memoization nedir: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
memoization |
Önbellek |
cache |
Sözlük |
subproblem |
Alt problem |
recursion |
Kendini çağırır |