📊 Rekürsif Analiz - Kısa Notlar

🔄 Yerine Koyma Metodu (Substitution)

Ne Zaman Kullanılır?

T(n) = T(n-1) + f(n) tipindeki rekürsiyonlar için

Örnek: T(n) = T(n-1) + n

Adımlar:

T(n) = T(n-1) + n
     = T(n-2) + (n-1) + n
     = T(n-3) + (n-2) + (n-1) + n
     = ...
     = T(0) + [1 + 2 + 3 + ... + n]

k adım sonra:

T(n) = T(n-k) + [(n-k+1) + ... + n]

Taban duruma ulaş: n-k = 0 → k = n

T(n) = T(0) + [1 + 2 + ... + n]
     = 1 + n(n+1)/2
     = O(n²)

Görselleştirme

foo(4) → 4 printf + foo(3)
         foo(3) → 3 printf + foo(2)
                  foo(2) → 2 printf + foo(1)
                           foo(1) → 1 printf + foo(0)

Toplam: 4+3+2+1 = 10 işlem = O(n²)

🎓 Master Teoremi

Format

T(n) = a·T(n/b) + f(n)
  • a = alt problem sayısı
  • b = problem küçültme faktörü
  • f(n) = bölme/birleştirme maliyeti

Kritik Değer

c_kritik = log_b(a)

3 Durum

Durum Koşul Sonuç
1 f(n) = O(n^(c_kritik - ε)) T(n) = Θ(n^c_kritik)
2 f(n) = Θ(n^c_kritik) T(n) = Θ(n^c_kritik · log n)
3 f(n) = Ω(n^(c_kritik + ε))+ Düzenlilik şartı T(n) = Θ(f(n))

Düzenlilik şartı: a·f(n/b) ≤ c·f(n) (0 < c < 1)

Hızlı Karar

f(n) ile n^c_kritik'i karşılaştır:

f(n) DAHA KÜÇÜK → Durum 1 → Rekürsif çağrılar kazanır
f(n) EŞİT      → Durum 2 → İkisi de eşit önemli
f(n) DAHA BÜYÜK → Durum 3 → f(n) kazanır

💡 Hızlı Örnekler

Merge Sort

T(n) = 2T(n/2) + n
a=2, b=2, f(n)=n
c_kritik = log₂(2) = 1
f(n) = n = Θ(n¹) → DURUM 2
→ T(n) = Θ(n log n)

T(n) = T(n/2) + 1
a=1, b=2, f(n)=1
c_kritik = log₂(1) = 0
f(n) = 1 = Θ(n⁰) → DURUM 2
→ T(n) = Θ(log n)

T(n) = 8T(n/2) + 1000n²

a=8, b=2, f(n)=1000n²
c_kritik = log₂(8) = 3
f(n) = 1000n² < n³ → DURUM 1
→ T(n) = Θ(n³)

Strassen

T(n) = 7T(n/2) + n²
a=7, b=2, f(n)=n²
c_kritik = log₂(7) ≈ 2.807
f(n) = n² < n^2.807 → DURUM 1
→ T(n) = Θ(n^2.807)

📋 Karşılaştırma Tablosu

Metod Ne Zaman Örnek
Yerine Koyma T(n) = T(n-1) + ... Faktöriyel
Master Teoremi T(n) = aT(n/b) + ... Merge Sort

🎯 Faydalı Formüller

Toplam formülleri:
1 + 2 + ... + n = n(n+1)/2 = O(n²)
1 + 2 + 4 + ... + 2ⁿ = 2^(n+1) - 1 = O(2ⁿ)

Logaritma kuralları:
log_b(a) = log(a) / log(b)
log(ab) = log(a) + log(b)
log(aᵇ) = b·log(a)

💪 Çözüm Stratejisi

Yerine Koyma için:

  1. İlk 3-4 adımı yaz
  2. Kalıbı gör
  3. Genel formu yaz
  4. k = n yap
  5. Toplam formülünü uygula

Master Teoremi için:

  1. a, b, f(n) belirle
  2. c_kritik hesapla
  3. f(n) ile n^c_kritik karşılaştır
  4. Durumu bul
  5. Sonucu yaz

⚠️ Dikkat Edilecekler

❌ Yapma:

  • log tabanını unutma
  • Epsilon (ε) şartını atla
  • Düzenlilik şartını kontrol etme (Durum 3)

✅ Yap:

  • Dominant terimi bul
  • Big-O, Ω, Θ farkını bil
  • Formülleri ezberle

🚀 Hızlı Referans

Notasyonlar:

  • O(f) → En fazla f
  • Ω(f) → En az f
  • Θ(f) → Tam olarak f

Yaygın Karmaşıklıklar:

O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(n³) < O(2ⁿ) < O(n!)

Merge Sort Ağacı:

        n iş
       /  \
    n/2   n/2    → Her seviye n iş
    / \   / \
   ... ... ... → log(n) seviye

Toplam: n · log(n)