Algoritma Nedir? Big-O Nasıl Okunur?

Bir kullanıcı listesinde belirli e-postayı bulmak için bütün kayıtları dolaşabiliriz. Bin kullanıcıda sorun görünmez; yüz milyon kullanıcıda aynı yaklaşım darboğaz olabilir. Algoritma analizi, kodu belirli bir bilgisayardan bağımsız olarak veri büyüdüğünde değerlendirmemizi sağlar.

Algoritma nedir?

Algoritma, bir problemi sonlu ve açık adımlarla çözen yöntemdir. İyi bir algoritma yalnızca doğru sonuç üretmez; zaman, bellek ve uygulanabilirlik kısıtlarını da karşılar.

Big-O, giriş boyutu n büyüdükçe kaynak kullanımının üst sınırdaki büyüme eğilimini anlatır. Kesin milisaniye vermez ve küçük girdilerde hangi kodun hızlı olduğunu tek başına söylemez.

function contains(values: number[], target: number): boolean {
  for (const value of values) {
    if (value === target) return true;
  }
  return false;
}

values dizisindeki her eleman en fazla bir kez incelenir. En kötü durumda hedef yoktur ve n karşılaştırma yapılır: zaman karmaşıklığı O(n) olur. Ek veri yapısı kullanılmadığı için alan karmaşıklığı O(1) kabul edilir.

Sık görülen sınıflar

O(1): Girdi büyüse de sabit sayıda işlem; dizide indeksle erişim.
O(log n): Her adımda problem sabit oranda küçülür. Binary search, sıralı dizinin ortasına bakıp aramanın yarısını her adımda elemesidir.
O(n): Her öğe bir kez işlenir.
O(n log n): Birçok verimli genel sıralama algoritması.
O(n²): Her öğenin diğerleriyle karşılaştırıldığı iç içe döngüler.

Katsayılar Big-O’da atılır: 3n + 20, O(n) olur. Ancak gerçek sistemde katsayı, cache davranışı ve ağ çağrısı önemlidir. Big-O seçim filtresidir; benchmark’ın yerine geçmez.

Daha iyi alternatif nasıl bulunur?

Aynı listede bir kez arama yapılacaksa O(n) tarama yeterlidir. Çok sayıda arama varsa listeyi Set yapısına dönüştürmek ortalama O(1) üyelik kontrolü sağlar, karşılığında ek bellek ve hazırlık maliyeti getirir. Veri sıralıysa binary search O(log n) sunar. Doğru seçenek arama sayısına, güncelleme sıklığına ve bellek sınırına bağlıdır.

Alıştırma

İki iç içe döngüyle listedeki tüm çiftleri üreten fonksiyonun zaman karmaşıklığını bulun. Sonra yalnızca komşu çiftler gerekse algoritmanın nasıl O(n) yapılacağını düşünün.