📘 Asimptotik Notasyonlar - Ders Notu

🎯 O-Notasyonu (Big-O) - Üst Sınır

Tanım: Algoritmanın en kötü durum performansını gösterir.

f(n) = O(g(n)) ⟺ ∃c > 0, ∃n₀ ≥ 0 : ∀n ≥ n₀ → f(n) ≤ c·g(n) + b

Basit açıklama: f(n) fonksiyonu, yeterince büyük n değerleri için c·g(n)‘den daha hızlı büyümez.

📝 Örnek Çözüm

Soru: T(n) = 32n² + 17n + 32 için Big-O’yu bulun.

Cevap: T(n) = O(n²)

Açıklama:

• En yüksek dereceli terim: n²
• Diğer terimler (n, sabitler) n→∞ iken ihmal edilir
• ✅ O(n²) → DOĞRU
• ✅ O(n³) → DOĞRU (üst sınır da olur)
• ❌ O(n) → YANLIŞ (alt sınır olamaz)

İspat Örneği

Verilen: f(n) = 5n³ + 2n² + 22n + 6
Göster: f(n) = O(n³)

Çözüm:

Hedef: 5n³ + 2n² + 22n + 6 ≤ c·n³ için c ve n₀ bul

n₀ = 0 dene:
  6 ≤ 0 → ❌ OLMAZ

n₀ = 1 dene:
  5(1)³ + 2(1)² + 22(1) + 6 = 35
  35 ≤ c·1³ → c = 35 seçilebilir ✅

SONUÇ: n₀ = 1, c = 35

📊 Diğer Notasyonlar

Ω-Notasyonu (Omega) - Alt Sınır

Algoritmanın en iyi durum performansını gösterir.

Θ-Notasyonu (Theta) - Sıkı Sınır

Hem üst hem alt sınırı gösterir (gerçek performans).

⚡ Karmaşıklık Seviyeleri

Hızdan yavaşa sıralama:

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

Tanımlar

🔥 Önemli Kurallar

1. Sabit Katsayılar İhmal Edilir

O(3n) = O(n)
O(n/2) = O(n)
O(100) = O(1)

2. En Büyük Terim Kazanır

O(n² + n) = O(n²)
O(5n³ + 2n² + 100n + 50) = O(n³)

3. Farklı Değişkenler Korunur

O(n + m) ≠ O(n)  ← n ve m farklı
O(n × m) ≠ O(n²) ← n ≠ m ise

💻 Kod Örnekleri

# O(1) - Sabit zaman
def get_first(arr):
    return arr[0]

# O(n) - Doğrusal zaman
def find_max(arr):
    max_val = arr[0]
    for num in arr:  # n kez döner
        if num > max_val:
            max_val = num
    return max_val

# O(n²) - Karesel zaman
def bubble_sort(arr):
    for i in range(len(arr)):        # n kez
        for j in range(len(arr)-1):   # n kez
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]

# O(log n) - Logaritmik zaman
def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            left = mid + 1
        else:
            right = mid - 1
    return -1

📊 Performans Karşılaştırması

n = 1,000,000 için tahmini işlem sayıları:

💡 Pratik kural: n > 10,000 için O(n²) algoritmaları çok yavaştır!

🎯 Sık Yapılan Hatalar

❌ Yanlış: O(n² + n) yazmak

✅ Doğru: O(n²)

❌ Yanlış: O(3n) ≠ O(n) demek

✅ Doğru: O(3n) = O(n)

❌ Yanlış: O(n + m) = O(n) demek

✅ Doğru: O(n + m) olarak bırak (n ≠ m)

📚 Yaygın Sıralama Algoritmaları

🔍 Hızlı Analiz İpuçları

Döngü sayısına bak:

• Tek döngü → O(n)
• İç içe 2 döngü → O(n²)
• İç içe 3 döngü → O(n³)

Özel durumlar:

• Her adımda yarıya iniyor → O(log n)
• Sıralama + arama → O(n log n)
• Tüm eleman çiftleri → O(n²)

📌 Sınav/Mülakat İpuçları

1. İspatlarda n₀ ve c bul (genelde n₀ = 1 yeterli)
2. En büyük terimi söyle (gerisi önemsiz)
3. Döngü sayısını say (hızlı analiz için)
4. Karşılaştırmalarda: küçük fonksiyon ≤ büyük fonksiyon