Fibonacci tabulation

Fibonacci'yi tabloyla hesaplamayı öğrenirsin.

Fibonacci tabulation

Fibonacci tabulation: bir dizi kur, dp[0]=0, dp[1]=1, sonra dp[i] = dp[i-1] + dp[i-2].

Bu, recursion'sız ve önbellek'siz Fibonacci hesaplar; çok verimlidir.

Tabulation, Θ(n) zaman ve Θ(n) bellek verir; tek değişkenle Θ(1) belleğe indirilebilir.

Bellek optimizasyonu

Sadece iki önceki değeri tutmak, tablonun tamamını saklamaya gerek kalmamasını sağlar; bellek Θ(1) olur.

Ancak tablo yöntemi, genel DP problemlerinde izi kolaylaştırır; bu yüzden öğretimde tercih edilir.

İki değişkenli çözüm, önbellek karmaşıklığından kurtulur; hızı korunur.

Uygulama Fibonacci optimizasyon

fib_opt(n) yaz. Sadece iki değişkenle Fibonacci hesapla. print(fib_opt(10)) ile 55 yazdır.

Örnek çözümü göster

def fib_opt(n):
    # Fibonacci optimizasyon
    if n <= 1:
        return n
    prev2 = 0
    prev1 = 1
    for i in range(2, n + 1):
        curr = prev1 + prev2
        prev2 = prev1
        prev1 = curr
    return prev1
print(fib_opt(10))

Kendini test et

Fibonacci tabulation: kavramları eşleştir

dp

Tablo
i-1

Önceki
i-2

İki önceki
O(n)

Doğrusal
Fibonacci tabulation bellek karmaşıklığı nedir?
- Θ(1)
- Θ(n)
- Θ(log n)
- Θ(n^2)
Cevabı göster

Θ(n) — Θ(n).

Döngü gövdesi

dp[i] = dp[i - 1] + dp[i - ____]

Cevabı göster

dp[i] = dp[i - 1] + dp[i - 2]

Sıradaki ders: Özet - Tabulation

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler