Memoization nedir?

Hesaplanan alt sonuçları saklayarak tekrar hesabı önlemeyi öğrenirsin.

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.

fib_naive(n) yaz. Recursive naive Fibonacci. print(fib_naive(10)) ile 55 yazdır.

Örnek çözümü göster

def fib_naive(n):
    # Naive Fibonacci
    if n <= 1:
        return n
    return fib_naive(n - 1) + fib_naive(n - 2)
print(fib_naive(10))