Çağrı ağacı

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.

Örnek çözümü göster

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))

Kendini test et

Çağrı ağacı: kavramları eşleştir

Çağrı ağacı

İkili ağaç
Tekrar

Üstel büyüme
fib(3)

İki kez
Memoization

Önbellek
Naive Fibonacci neden yavaştır?
- Az çağrı yapar
- Aynı alt problemleri tekrar hesaplar
- Bellek az kullanır
- Döngü yok
Cevabı göster

Aynı alt problemleri tekrar hesaplar — Aynı alt problemleri tekrar hesaplar.

Tekrar

Aynı alt problem ____ hesaplanır.

Cevabı göster

Aynı alt problem tekrar hesaplanır.

Sıradaki ders: Özet - Fibonacci

Deneyiminizi Geliştiriyoruz

Çerez Tercihleri

Kesinlikle Gerekli Çerezler

Analitik Çerezler