Çağrı ağacı
- Algoritmalar kursu
- Başlangıç
- Ders 43/80
- 4 dk
Recursive Fibonacci'nin tekrarlı çağrılarla verimsiz olduğunu öğrenirsin.
Çağrı ağacı
Recursive Fibonacci'nin çağrı ağacı, her düğümün iki çocuk yaptığı bir ikili ağaçtır. Aynı değerler defalarca hesaplanır.
Örneğin fib(5) çağrısı fib(3)'ü iki kez, fib(2)'yi üç kez hesaplar. Bu tekrar, üstel karmaşıklığın nedenidir.
Tekrar sorunu
Naive Fibonacci'nin en büyük sorunu, aynı alt problemleri tekrar tekrar hesaplamasıdır. fib(3) hem fib(4) hem fib(5) tarafından çağrılır.
Bu tekrar, daha ileri seviyede memoization ile çözülür. Hesaplanan değerler önbelleğe alınır ve tekrar hesaplanmaz.
Uygulama Fibonacci listesi
fib_list(n) yaz. n+1 elemanlı Fibonacci dizisi döndür. print(fib_list(5)) ile [0, 1, 1, 2, 3, 5] yazdır.
Başlangıç kodu
def fib_list(n):
# Fibonacci listesiÖrnek çözüm
def fib_list(n):
# Fibonacci listesi
if n == 0:
return [0]
result = [0, 1]
for i in range(2, n + 1):
result.append(result[i-1] + result[i-2])
return result
print(fib_list(5))Beklenen çıktı
[0, 1, 1, 2, 3, 5]
Soru ve cevaplar
Dersin sorularını cevaplarıyla birlikte inceleyebilirsin. Kendini denemek istersen dersi interaktif olarak çöz.
1 Çağrı ağacı: kavramları eşleştir
| Kavram | Anlamı |
|---|---|
Çağrı ağacı |
İkili ağaç |
Tekrar |
Üstel büyüme |
fib(3) |
İki kez |
Memoization |
Önbellek |
2 Naive Fibonacci neden yavaştır?
- Az çağrı yapar
- Aynı alt problemleri tekrar hesaplar Doğru cevap
- Bellek az kullanır
- Döngü yok
Açıklama: Aynı alt problemleri tekrar hesaplar.
3 Tekrar
Aynı alt problem ____ hesaplanır.Aynı alt problem tekrar hesaplanır.Açıklama: tekrar doğru.