Fibonacci ve Memoization

#Nasıl çalışır?

Dinamik programlama (DP), bir problemi örtüşen alt problemlere bölüp her alt problemi yalnızca bir kez çözen bir tekniktir. Fibonacci sayıları (0, 1, 1, 2, 3, 5, 8, …) bunu görmenin en kolay yoludur: fib(n) = fib(n − 1) + fib(n − 2).

Tanımı doğrudan özyinelemeye çevirmek doğru sonucu verir ama aynı değerleri defalarca hesaplar. fib(5) için fib(2) üç kez, fib(3) iki kez hesaplanır; çağrı sayısı n ile üstel büyür ve fib(50) için milyarlarca çağrı gerekir.

Memoization (yukarıdan aşağı DP) özyinelemeyi korur ama her sonucu bir önbelleğe yazar; aynı değer tekrar istendiğinde hesaplamadan döndürür. Tablo yöntemi (alttan yukarı DP) ise özyinelemeyi tamamen bırakıp küçük değerlerden büyüğe doğru bir dizi doldurur.

Bir problemin DP ile çözülebilmesi için iki özellik gerekir: örtüşen alt problemler (aynı alt problem tekrar tekrar çıkar) ve optimal alt yapı (büyük problemin cevabı alt problemlerin cevaplarından kurulur).

#Kendin dene

#Adım adım

1. 01Durumu tanımla: dp[i] = i. Fibonacci sayısı.
2. 02Temel durumları yaz: dp[0] = 0, dp[1] = 1.
3. 03Geçişi yaz: dp[i] = dp[i − 1] + dp[i − 2].
4. 04Hesaplama sırasını seç: memoization (özyineleme + önbellek) ya da tablo (küçükten büyüğe döngü).

#Örnek kod

Aynı algoritma 8 dilde. Her program derlenip çalıştırılarak test edildi ve hepsi aynı çıktıyı veriyor.

def fib_naive(n: int) -> int:
    """Plain recursion: correct, but O(2^n) calls."""
    return n if n < 2 else fib_naive(n - 1) + fib_naive(n - 2)


memo = {}


def fib_memo(n: int) -> int:
    """Top-down DP: every value is computed once and cached."""
    if n < 2:
        return n
    if n not in memo:
        memo[n] = fib_memo(n - 1) + fib_memo(n - 2)
    return memo[n]


def fib_table(n: int) -> int:
    """Bottom-up DP with only the last two values: O(n) time, O(1) memory."""
    a, b = 0, 1  # fib(0), fib(1)
    for _ in range(n):
        a, b = b, a + b
    return a


print(fib_naive(10))  # fine for small n; fib_naive(40) would take seconds
print(fib_memo(40))
print(fib_table(50))
# Python can also memoize for you: functools.lru_cache on fib_naive.

#Karmaşıklık

Düz özyinelemenin çağrı sayısı 2·fib(n + 1) − 1'dir ve yaklaşık 1,6ⁿ hızında büyür. DP her değeri bir kez hesapladığı için doğrusaldır. Matris üssü yöntemiyle fib(n) O(log n) zamanda da hesaplanabilir.

#Ne zaman kullanılır?

Memoization, özyinelemeli çözümü kolay yazılan ama alt problemleri tekrar eden her problemde ilk denenecek tekniktir. Tablo yöntemi derin özyinelemeden (yığın taşması) kaçınmak ve belleği küçültmek için tercih edilir. Merdiven çıkma, yol sayma ve bozuk para sayısı gibi problemler aynı kalıptadır.

#Alıştırma

Soruları cevaplamak ve ilerlemeni kaydetmek için giriş yap.

#Bundan sonra

Bu dersi bildiğini varsayan dersler:

• Floyd-Warshall Algoritması
• 0/1 Sırt Çantası (Knapsack)
• En Uzun Ortak Alt Dizi (LCS)
• En Uzun Artan Alt Dizi (LIS)