Big-O Notasyonu: Sadece Teori Değil, Gerçek Kodla Anlatım

Big-O notasyonu, ders kitabında korkutucu görünen ama yeterince kod gördükten sonra apaçık hâle gelen konulardan biri. Tek amaç şu: bir algoritmanın çalışma süresinin girdi büyüdükçe nasıl arttığını tanımlamak — sabitler ve küçük terimler büyük ölçekte önemini yitirdiği için göz ardı edilir.

Fonksiyonun 10 elemanda 1 ms, 10.000 elemanda 5 saniye sürüyorsa, bu büyüme oranının kabul edilebilir mi yoksa üretim sunucunu çökertecek mi olduğunu sana söyleyen şey Big-O'dur.

Pratikte gerçekten gördüğün beş sınıf

• O(1) — sabit zaman. İşin girdi büyüklüğüne bağlı değil. Hash map'ten anahtar bakmak, önceden hesaplanmış bir değeri döndürmek.
• O(log n) — logaritmik. Her adım girdinin yarısını eler. İkili arama, dengeli ağaçlarda arama.
• O(n) — doğrusal. Her elemana bir kez dokunursun. Diziyi tek for-döngüsüyle dolaşmak.
• O(n log n) — n log n. Girdiyi özyinelemeli olarak parçalar, her seviyede doğrusal iş yaparsın. Merge sort, heap sort, modern hızlı sıralayıcıların çoğu.
• O(n²) — karesel. Aynı diziyi gezen iç içe iki döngü. Kötü sıralama algoritmaları, her çiftin karşılaştırması.

Karmaşıklığı koddan çıkarmanın hızlı yolu

Formal kanıtı bir an için unut. Pratikte vakaların %90'ında işe yarayan tembel yöntem şudur: döngüleri ve neyi gezdiklerini say.

O(1) — sabit

function getFirst(arr) { return arr[0]; } — döngü yok, özyineleme yok, büyüme yok. Hep tek işlem.

O(n) — doğrusal

function sum(arr) { let total = 0; for (const x of arr) total += x; return total; } — tek döngü, eleman başına bir kez döner.

O(n²) — karesel

function hasDuplicate(arr) { for (let i = 0; i < arr.length; i++) for (let j = i + 1; j < arr.length; j++) if (arr[i] === arr[j]) return true; return false; } — iç içe iki döngü, ikisi de n'e kadar gider. 10.000 eleman için 50 milyon karşılaştırma. 100.000 eleman için 5 milyar. Sunucunu çökerten fonksiyon işte budur.

O(log n) — logaritmik

Sıralı bir dizide ikili arama. Ortadaki elemana bakarsın, yarısını atarsın, kalanın ortasına bakarsın, yine yarısını atarsın. Bir milyon eleman için yalnızca 20 civarı karşılaştırma. T(n) = T(n/2) + O(1) tekrarlaması O(log n) verir.

O(n log n) — hızlı sıralama

Merge sort diziyi yarıya böler (log n seviye), her seviyede yarıları birleştirir (her seviyede doğrusal iş). Toplam: n log n. Quick sort ortalama aynı sınıfa düşer. JavaScript'te Array.prototype.sort, Python'da sorted, Java'da Collections.sort hep O(n log n) sebebi budur.

Sabitler neden önemsiz (önemli olduğu zamana kadar)

Big-O sabitleri atar: O(2n), O(n) ile aynıdır; O(100n) yine O(n)'dir. Asimptotik analiz için doğrudur — n yeterince büyüyünce her sabiti geçer. Ama gerçek sistemlerde 100 katlık sabit önemlidir, özellikle girdi sınırlıysa. Hem sınıfı hem pratik sabiti bilmek, mülakattaki doğru cevapla üretimde çalışan sistem arasındaki farktır.

Yavaş kodu pratikte tanımak

• Aynı koleksiyonu gezen iki iç içe döngü → O(n²). Birini hash set veya sıralı diziyle sıkıştırmak mümkün mü, sor.
• Döngü içinde .indexOf() veya .includes() → yine O(n²), çünkü indexOf'un kendisi O(n). Set kullan.
• Döngü içinde sıralama → O(n² log n). Sıralamayı döngünün dışına al, bir kez yap.
• Aynı boyutta kendini iki kez çağıran özyineleme → üstel. Sonuçları belleğe al (memoization) ya da iteratif yaz.

Somut bir iyileştirme

Saf yinelenen eleman tespiti O(n²)'dir. İç döngüyü Set bakışı ile değiştirince O(n) olur: function hasDuplicate(arr) { const seen = new Set(); for (const x of arr) { if (seen.has(x)) return true; seen.add(x); } return false; } — aynı cevap, büyük girdide muazzam fark.

Bir fonksiyonu Solvequill'e yapıştırırsan, açıklama videosu döngüleri tek tek geziyor, ekrandaki karmaşıklık sınıfını adlandırıyor ve darboğazın nerede olduğunu işaret ediyor. Teorik kanıtlardan geçmeden sezgi kurmanın hızlı yollarından biri.