Big O Notasyonu Nedir? Algoritma Karmaşıklığı Örneklerle

Big O notasyonu, bir algoritmanın girdi boyutu (n) büyüdükçe çalışma süresinin veya kullandığı belleğin en kötü durumda hangi hızla arttığını ifade eden gösterimdir. Örneğin O(n) yazılması, veri iki katına çıktığında çalışma süresinin de yaklaşık iki katına çıktığı anlamına gelir. O(n²) ise veri iki katına çıktığında sürenin yaklaşık dört katına çıktığını gösterir. Big O, saniye ölçmez. Büyüme hızını ölçer.

Bu yazıda Big O notasyonunun temel kurallarını, en yaygın karmaşıklık sınıflarını, her biri için kod örneklerini, bellek karmaşıklığını ve günlük projelerde yavaş çalışan kodu hızlandırmak için bu bilginin nasıl kullanılacağını ele alacağız.

Big O Notasyonu Neden Önemlidir?

Bir kodun çalışma süresi bilgisayardan bilgisayara, programlama dilinden dile değişir. Bu yüzden iki algoritmayı saniye cinsinden karşılaştırmak yanıltıcıdır. Big O, donanımdan bağımsız olarak algoritmanın ölçeklenme davranışını anlatır.

Test ortamında yüz kayıtla anında çalışan bir kod, canlı ortamda yüz bin kayıtla dakikalarca sürebilir. Big O bilgisi, bu sorunu kod yazılırken fark etmeyi sağlar.

Big O Hesaplanırken Hangi Kurallar Uygulanır?

• Sabitler atılır: 3n adım O(n), n/2 adım yine O(n) olarak yazılır.
• Baskın terim alınır: n² + 5n + 100 ifadesi O(n²) olur, çünkü n büyüdükçe diğer terimler önemsizleşir.
• En kötü durum esas alınır: Aranan eleman listenin ilk sırasında bulunsa bile doğrusal aramanın karmaşıklığı O(n) kabul edilir.
• Ardışık bloklar toplanır, iç içe bloklar çarpılır: Art arda iki döngü O(n + n) = O(n), iç içe iki döngü O(n x n) = O(n²) olur.

En Yaygın Karmaşıklık Türleri Nelerdir?

Tablodaki değerler yaklaşık adım sayılarıdır. n bin olduğunda O(n) ile O(n²) arasındaki farkın bin kata ulaştığına dikkat edin. Bu fark, kayıt sayısı arttıkça daha da açılır.

O(1) Sabit Zaman Nedir?

İşlem süresi veri boyutundan bağımsızsa karmaşıklık O(1) olur. Dizinin birinci elemanını okumak, dizide on eleman da olsa on milyon eleman da olsa aynı sürede gerçekleşir.

<?php
function ilkEleman(array $liste) {
    return $liste[0] ?? null;   // O(1)
}

$fiyatlar = ['elma' => 25, 'armut' => 30];
echo $fiyatlar['armut'];        // Anahtarla erişim: ortalama O(1)

O(n) Doğrusal Zaman Nedir?

Her elemanın bir kez işlendiği algoritmalar doğrusaldır. Veri iki katına çıkınca süre de yaklaşık iki katına çıkar.

<?php
function enBuyuk(array $sayilar) {
    $max = $sayilar[0];
    foreach ($sayilar as $s) {          // n adım
        if ($s > $max) $max = $s;
    }
    return $max;                        // O(n)
}

O(n²) Karesel Zaman Nedir?

İç içe iki döngü, her eleman için tüm elemanları tekrar dolaşır. Küçük verilerde fark edilmez, ancak büyük verilerde ciddi yavaşlamaya yol açar.

<?php
// Listede tekrar eden değer var mı? O(n²) çözüm
function tekrarVarMi(array $liste) {
    $n = count($liste);
    for ($i = 0; $i < $n; $i++) {
        for ($j = $i + 1; $j < $n; $j++) {
            if ($liste[$i] === $liste[$j]) return true;
        }
    }
    return false;
}

O(log n) Logaritmik Zaman Nedir?

Her adımda arama alanını yarıya indiren algoritmalar logaritmiktir. En bilinen örnek, sıralı dizide ikili aramadır. Bin elemanlı sıralı listede en fazla yaklaşık on karşılaştırma ile sonuca ulaşılır.

<?php
function ikiliArama(array $sirali, int $aranan) {
    $sol = 0;
    $sag = count($sirali) - 1;

    while ($sol <= $sag) {
        $orta = intdiv($sol + $sag, 2);
        if ($sirali[$orta] === $aranan) return $orta;
        if ($sirali[$orta] < $aranan) $sol = $orta + 1;
        else $sag = $orta - 1;
    }
    return -1;                          // O(log n)
}

Veritabanlarındaki B-Tree indexler de aynı prensiple çalışır. Milyonlarca satır arasında aranan kaydın birkaç adımda bulunmasının sebebi logaritmik aramadır.

O(n log n) Nedir?

Birleştirmeli sıralama (merge sort) ve hızlı sıralamanın (quick sort) ortalama durumu gibi verimli sıralama algoritmaları O(n log n) karmaşıklığındadır. Karşılaştırmaya dayalı sıralamada ulaşılabilecek en iyi genel sınır budur. PHP sort() ve C# Array.Sort() fonksiyonları da bu sınıfta çalışır. Bu yüzden kendi sıralama algoritmanızı yazmak yerine dilin hazır fonksiyonlarını kullanmak çoğu zaman en doğru tercihtir.

O(n²) Algoritma O(n) Hale Nasıl Getirilir?

Performans iyileştirmelerinin büyük kısmı, iç içe döngüyü karma tablo (hash table) kullanarak tek döngüye indirmektir. Yukarıdaki tekrar kontrolünün doğrusal sürümü:

<?php
function tekrarVarMiHizli(array $liste) {
    $gorulen = [];
    foreach ($liste as $deger) {
        if (isset($gorulen[$deger])) return true;   // ortalama O(1)
        $gorulen[$deger] = true;
    }
    return false;                                    // toplam O(n)
}

Aynı yaklaşım C# tarafında HashSet ile uygulanır:

static bool TekrarVarMi(IEnumerable<string> liste)
{
    var gorulen = new HashSet<string>();
    foreach (var deger in liste)
    {
        if (!gorulen.Add(deger)) return true;   // Add, eleman varsa false döner
    }
    return false;
}

Bu dönüşümün bedeli ek bellek kullanımıdır. Zaman kazanmak için bellek harcamak, algoritma tasarımında sık yapılan bilinçli bir takastır.

Bellek Karmaşıklığı Nedir?

Big O yalnızca süreyi değil, algoritmanın ek olarak ihtiyaç duyduğu belleği de ifade eder. Yukarıdaki ilk tekrar kontrolü ek bellek kullanmadığı için O(1) bellek karmaşıklığındadır. Hızlı sürüm ise görülen değerleri sakladığı için O(n) bellek kullanır.

Sahadan Gözlem: İki Listeyi Karşılaştırmak

Fabrikada stok kayıtlarını dışarıdan gelen bir Excel listesiyle karşılaştıran küçük bir araç yazmıştık. İlk sürümde her Excel satırı için stok listesinin tamamı döngüyle taranıyordu. Test verisinde sorun görünmedi. Gerçek listeler yüklendiğinde ise işlem dakikalarca sürdü.

Kod incelendiğinde yapının iki listenin boyutlarının çarpımı kadar adım attığı, yani karesel büyüdüğü görüldü. Stok listesi önce ürün koduna göre anahtarlı bir diziye dönüştürüldü, ardından Excel satırları bu dizide anahtarla arandı. İşlem doğrusal hale geldi ve karşılaştırma bekleme gerektirmeden tamamlanır oldu. Kodun geri kalanında hiçbir değişiklik yapılmadı. Fark yalnızca doğru veri yapısını seçmekten geldi.

Big O Hakkında Sık Yapılan Yanlışlar

• Big O gerçek süreyi vermez: O(n) bir algoritma, küçük verilerde O(n²) bir algoritmadan yavaş olabilir. Big O büyük veriler için eğilimi gösterir.
• Dil fonksiyonları bedava değildir: PHP in_array() veya C# List.Contains() fonksiyonları döngü içinde kullanıldığında gizli bir O(n²) oluşturur.
• Veritabanı sorguları da sayılır: Döngü içinde her satır için ayrı sorgu çalıştırmak, uygulama tarafında görünmeyen ama ciddi bir yük oluşturur.