Doğadaki ayçiçeklerinin çekirdek diziliminden çam kozalaklarına, deniz kabuklarının sarmal kıvrımlarından Mimar Sinan'ın başyapıtlarındaki estetik oranlara kadar evrenin dört bir yanında karşımıza çıkan **Fibonacci Sayı Dizisi**, bilgisayar bilimlerinde çok özel bir yere sahiptir. Ancak Fibonacci dizisi, yazılımcılar için yalnızca büyüleyici bir matematiksel merak konusu değildir; aynı zamanda bir yazılımın işlemciyi nasıl kitleyebileceğini ve bu kilitlenmenin **Dinamik Programlama (Dynamic Programming - DP)** tekniğiyle nasıl saliseler içinde çözülebileceğini gösteren en meşhur pedagojik örnektir.
---
1. Fibonacci Dizisi Nedir?
1202 yılında İtalyan matematikçi Leonardo Fibonacci tarafından tavşan popülasyonunun artışını modellemek için ortaya atılan dizi, kendisinden önceki iki sayının toplamıyla ilerleyen bir sayı dizisidir:
$$0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, \dots$$
Matematiksel Tanım (Özyinelemeli / Recursive Formül):
---
2. Klasik Özyineleme (Recursion) Tuzağı ve $O(2^n)$ Felaketi
Bir yazılımcı bu matematiksel formülü görür görmez bilgisayarda doğrudan özyinelemeli (kendini çağıran) bir fonksiyon yazma eğilimindedir:
def fib_yavas(n):
if n <= 1:
return n
return fib_yavas(n - 1) + fib_yavas(n - 2)Bu fonksiyon $n=10$ veya $n=20$ için anında sonuç verir. Ancak $n=50$ yazdığınız anda bilgisayarınızın işlemci fanı çılgınca dönmeye başlar ve program dakikalarca bitmez! Hatta $n=100$ yaparsanız evrenin ömrü bile sonucun hesaplanmasına yetmez.
Neden Bu Kadar Yavaş?
Çünkü aynı alt problemler milyonlarca kez gereksiz yere baştan hesaplanır!
Örneğin $F(5)$'i hesaplarken oluşan çağrı ağacına bakın:
---
3. Dinamik Programlamanın Kurtarıcı Felsefesi
1950'lerde Richard Bellman tarafından geliştirilen Dinamik Programlama (DP) mantığının özü tek bir altın kurala dayanır:
> **"Geçmişini hatırlamayanlar, onu tekrarlamak zorunda kalırlar!"**
Eğer bir problemi çözerken aynı alt problemle (Overlapping Subproblems) tekrar tekrar karşılaşıyorsanız, bulduğunuz sonucu bir tabloya veya belleğe kaydedin (Memoization). Bir dahaki sefere aynı soru sorulduğunda tekrar hesaplamak yerine tablodan anında cevabı çekin ($O(1)$ erişim süresi)!
İki Temel Dinamik Programlama Yaklaşımı:
1. **Yukarıdan Aşağıya (Top-Down / Memoization):** Problemi en tepeden başlayarak özyinelemeyle alt parçalara böleriz; ancak hesaplanan her değeri bir sözlükte (hash map) saklarız.
2. **Aşağıdan Yukarıya (Bottom-Up / Tabulation):** En küçük taban durumlarından ($F(0)$ ve $F(1)$) başlayarak bir döngü ile ileriye doğru doldurarak gideriz.
---
4. Karşılaştırmalı Performans Analizi
| Yöntem | Zaman Karmaşıklığı | Alan Karmaşıklığı | $F(50)$ Hesaplama Süresi |
|---|---|---|---|
| **Saf Özyinelemeli (Naive Recursive)** | $O(2^n)$ | $O(n)$ | ~ 30 Dakika |
| **Yukarıdan Aşağıya (DP Memoization)** | $O(n)$ | $O(n)$ | **0.0001 Saniye** |
| **Aşağıdan Yukarıya (DP Tabulation)** | $O(n)$ | $O(n)$ | **0.0001 Saniye** |
| **Optimize Edilmiş Alan DP** | $O(n)$ | $O(1)$ | **0.00005 Saniye** |
---
5. Tam ve Çalışan Python ve C++ Kodları
Python ile Bellek Tasarruflu Dinamik Programlama ($O(n)$ Zaman, $O(1)$ Alan):
def fib_dinamik_optimize(n):
if n <= 1:
return n
# Tüm diziyi saklamak yerine sadece son iki sayıyı tutmak yeterlidir!
prev2 = 0 # F(n-2)
prev1 = 1 # F(n-1)
for i in range(2, n + 1):
curr = prev1 + prev2
prev2 = prev1
prev1 = curr
return prev1
# Test Senaryosu
n = 50
print(f"Fibonacci({n}) Sonucu : {fib_dinamik_optimize(n)}")C++ ile Belleklemeli (Memoization) Dinamik Programlama:
#include <iostream>
#include <vector>
std::vector<long long> memo;
long long fibMemo(int n) {
if (n <= 1) return n;
if (memo[n] != -1) return memo[n]; // Zaten hesaplandıysa tablodan çek!
memo[n] = fibMemo(n - 1) + fibMemo(n - 2);
return memo[n];
}
int main() {
int n = 70;
memo.assign(n + 1, -1);
std::cout << "Fibonacci(" << n << ") = " << fibMemo(n) << std::endl;
return 0;
}---
6. Dinamik Programlamanın Gerçek Hayat Uygulamaları
---
7. Kendini Geliştirme Görevi (Challenge)
**Merdiven Çıkma Problemi:** $N$ basamaklı bir merdivenin en üstüne çıkmak istiyorsunuz. Her seferinde ya 1 basamak ya da 2 basamak atlayabilirsiniz. $N$ basamaklı bir merdiveni kaç farklı kombinasyonla çıkabileceğinizi hesaplayan bir dinamik programlama fonksiyonu yazın! (İpucu: Basamak sayılarının çözüm örüntüsünü $N=1, 2, 3, 4$ için incelediğinizde karşınıza hangi sayılar çıkıyor?).
---
---
8. İleri Seviye Yaklaşım: Matris Üs Alma ile $O(\log n)$ Sürede Fibonacci
Dinamik programlama $O(n)$ süresiyle muazzam bir hız sunsa da, $N = 10^{18}$ gibi astronomik sayılarda doğrusal döngü bile yavaş kalır. Bilgisayar bilimlerinde lineer cebir ve matris çarpımı kullanılarak Fibonacci sayıları **$O(\log n)$** sürede hesaplanabilir:
$$egin{pmatrix} F_{n+1} & F_n \ F_n & F_{n-1} \end{pmatrix} = egin{pmatrix} 1 & 1 \ 1 & 0 \end{pmatrix}^n$$
Matrisin $n$. kuvveti, ikili üs alma (Binary Exponentiation) yöntemiyle tıpkı İkili Arama gibi her adımda üssü ikiye bölerek logaritmik sürede hesaplanır. Bu ileri teknik, uluslararası algoritma olimpiyatlarında (IOI) ve kriptografik anahtar üretiminde en yüksek puan kazandıran yöntemlerden biridir.
---
Sonuç
Dinamik programlama, bilgisayar mühendisliği mülakatlarının ve algoritmik yarışmaların en kritik konularından biridir. Fibonacci dizisi üzerinden kavranan bu bellek-zaman optimizasyonu mantığı, yazılımlarınızı amatörlükten çıkarıp profesyonel yüksek performans standartlarına taşıyacaktır. Sitemizdeki diğer [Algoritma Rehberlerini](/dersler) incelemeyi unutmayın!