Fibonacci tabulation
- Algoritmalar kursu
- İleri seviye
- Ders 7/56
- 4 dk
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.
Başlangıç kodu
def fib_opt(n):
# Fibonacci optimizasyonÖrnek çözüm
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))Beklenen çıktı
55
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Fibonacci tabulation: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
dp |
Tablo |
i-1 |
Önceki |
i-2 |
İki önceki |
O(n) |
Doğrusal |
2 Fibonacci tabulation bellek karmaşıklığı nedir?
- Θ(1)
- Θ(n) Doğru cevap
- Θ(log n)
- Θ(n^2)
Açıklama: Θ(n).
3 Döngü gövdesi
dp[i] = dp[i - 1] + dp[i - ____]dp[i] = dp[i - 1] + dp[i - 2]Açıklama: 2 doğru.