Fibonacci memoization

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.

Örnek çözümü göster

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, {}))

Kendini test et

Önbellek kontrolü
```
if n in ____:
```
Cevabı göster
```
if n in memo:
```
Fibonacci memoization: kavramları eşleştir

memo

Önbellek
dict

Sözlük
n

Parametre
return

Döndür
Fibonacci memoization karmaşıklığı nedir?
- Θ(log n)
- Θ(2^n)
- Θ(n^2)
- Θ(n)
Cevabı göster

Θ(n) — Θ(n).

Sıradaki ders: Sözlük tabanlı önbellek

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler