Temeller
Toplamlar ve seriler
Merge sort ve heap analizini temellendiren aritmetik ve geometrik seriler.
Soru: merge sort neden O(n log n) de O(n²) değil?
İç içe gibi görünen kısım aslında her seviyede n iş ve log n seviye. Bu sayfa, “seviyelerin toplamı” ve “iç içe döngülerin toplamı” arasındaki farkı aritmetik ve geometrik seri üzerinden açar. Merge sort cevabı: n log n, n² değil.
Sayılarla
| n | 1+2+…+n | ≈ n² | 1+2+4+… (log n seviye) | ≈ 2n |
|---|---|---|---|---|
| 8 | 36 | 64 | 15 | 16 |
| 64 | 2080 | 4096 | 127 | 128 |
| 1024 | ~5·10⁵ | ~10⁶ | 2047 | 2048 |
Aritmetik seri n ile karesel arasında; geometrik seri 2n’de tavan yapar. Merge sort her seviyede n iş yapar ve log n seviye vardır, yani toplam n · log n.
Nereden gelir?
Aritmetik seri: 1 + 2 + … + n
İç içe iki döngü, dış 1..n, iç ortalama n/2: toplam 1 + 2 + … + n = n(n+1)/2 ≈ n²/2. Sabiti at, O(n²). Naif çift-gezin çözümlerin (iki elemanı karşılaştır) maliyeti budur.
Geometrik seri: 1 + 2 + 4 + … + 2ᵏ
Toplam 2ᵏ⁺¹ - 1. n = 2ᵏ alırsan 2n - 1 → O(n). Ağaç seviyelerinin boyutları 1, 2, 4, … n şeklinde katlanır; tamamı toplamı lineerdir. Bu yüzden bir böl-yönet ağacının tüm seviyelerini tek seferde gezmek O(n), O(n²) değil.
Bunları birleştir: merge sort
Her seviyede yapılan iş, o seviyedeki alt dizilerin birleştirilmesidir. Seviye başına iş = n. Seviye sayısı = log₂ n (her seviye yarıya bölüyor). Toplam: n · log n. Yani merge sort’taki “toplam iş” seviye sayısı × seviye başına iş’tir, iç içe döngü çarpımı değildir.
Tuzak: “toplam seviye boyutu n, n log n olamaz”
Bu, tek bir yol ile tüm seviyeleri karıştırmaktan gelir. Bir yolda inmek O(log n) (binary search gibi). Ama merge sort’ta her seviyenin tamamını gezersin, yani n iş × log n seviye = n log n. “Bir yol O(log n), tüm ağaç O(n)” derken merge sort’un n log n’ini kaçırmamalısın: tek yolu değil, tüm ağacı birleştiriyorsun.
Sıradaki adım
- Logaritmalar: log n seviye neden küçük.
- Karmaşıklık ve Big-O: döngü saymanın pratik hâli.
- Büyüme hızları: üç seriyi tek grafikte.
Alıştırma
Aşağıdaki grafiği n = 64’e getir. n² (aritmetik seri) ven log n (merge sort) değerlerini tahmin et. Şimdi n = 1024’e çıkar: n² kaç kat büyüdü, n log n kaç kat? Bu fark, neden mülakatta her zaman n log n isteyip n² seçmediğini gösterir.