Big O Notasyonu ve Zaman Karmaşıklığı: Örneklerle Rehber

Big O notasyonu, bir algoritmanın çalışma süresinin ya da bellek kullanımının girdi büyüdükçe nasıl büyüdüğünü anlatır. "Bu kod kaç saniye sürer?" sorusuna değil, "girdi iki katına çıkarsa iş kaç katına çıkar?" sorusuna cevap verir. Algoritma derslerinin vize ve finallerinde iki biçimde karşına çıkar: "bu kodun karmaşıklığını bulun" ve "şu iki algoritmayı karşılaştırın". Bu rehberde önce sezgiyi, sonra kesin tanımı, ardından döngü ve özyineleme analizini ve çözümlü alıştırmaları veriyorum.

Örnekler C# ile yazılı; sözdizimi yabancı geliyorsa C# sınıf ve nesne kavramı yazısı yeterli bir başlangıçtır, ama buradaki döngüler hemen her dilde aynıdır.

Sezgi: Saniyeyi Değil Büyümeyi Ölçüyoruz

Aynı kod farklı bilgisayarda farklı sürede çalışır; o yüzden saniye saymak algoritmayı değil makineyi ölçer. Bunun yerine temel işlem sayısını girdi boyutu n cinsinden yazarız. Diyelim ki bir kod 3n² + 5n + 2 işlem yapıyor. n = 1000 için 3n² terimi 3.000.000, 5n terimi 5.000'dir: büyük n'de tabloyu n² belirler. Sabit çarpan 3 de makineye ve derleyiciye göre değişir. İkisini de atarız ve "bu algoritma O(n²)" deriz.

Kesin Tanım ve O, Ω, Θ Farkı

f(n) = O(g(n)) demek, öyle c > 0 ve n₀ sabitleri var demektir ki her n ≥ n₀ için f(n) ≤ c·g(n) olur. Yukarıdaki örnekte c = 4, n₀ = 6 seçilebilir: n ≥ 6 için 5n + 2 ≤ n², dolayısıyla 3n² + 5n + 2 ≤ 4n².

• O (büyük O) üst sınırdır: "en fazla bu kadar hızlı büyür".
• Ω (omega) alt sınırdır: "en az bu kadar hızlı büyür".
• Θ (teta) ikisi birdendir: "tam bu hızda büyür".

Önemli ayrıntı: 3n² + 5n + 2 aynı zamanda O(n³)'tür; doğru ama gevşek bir sınırdır. Sınavda senden beklenen sıkı sınırdır, yani aslında Θ; gündelik dilde buna da "Big O" denir. Bu üç sembol en iyi/en kötü durum kavramlarından bağımsızdır; bu karışıklığa hatalar bölümünde döneceğim.

Yaygın Karmaşıklık Sınıfları

Yavaş büyüyenden hızlıya: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!).

// O(1): girdi boyutundan bağımsız
static int First(int[] a) => a[0];

// O(log n): her adımda aralık yarıya iner (dizi sıralı olmalı)
static int BinarySearch(int[] a, int target)
{
    int low = 0, high = a.Length - 1;
    while (low <= high)
    {
        int mid = low + (high - low) / 2;
        if (a[mid] == target) return mid;
        if (a[mid] < target) low = mid + 1;
        else high = mid - 1;
    }
    return -1;
}

// O(n): her elemana bir kez bakılır
static long Sum(int[] a)
{
    long total = 0;
    foreach (int x in a) total += x;
    return total;
}

// O(n²): her çift kontrol edilir
static int CountEqualPairs(int[] a)
{
    int count = 0;
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
            if (a[i] == a[j]) count++;
    return count;
}

// O(2ⁿ): her çağrı iki yeni çağrı doğurur
static long Fib(int n) => n < 2 ? n : Fib(n - 1) + Fib(n - 2);

O(n log n) sınıfının tipik örneği merge sort'tur; izini ve diğer sıralama algoritmalarıyla karşılaştırmasını sıralama algoritmaları sınav soruları yazısında bulabilirsin.

Döngüler Nasıl Analiz Edilir?

Dört kural işin büyük kısmını çözer:

1. Art arda gelen bloklar toplanır: O(n) + O(n²) = O(n²).
2. İç içe döngüler çarpılır, ama yalnızca iç döngünün tur sayısı dıştakinden bağımsızsa: n × m tur.
3. Sayaç çarpılıyor ya da bölünüyorsa (i *= 2, i /= 2) döngü log₂ n tur atar.
4. İç döngü dış sayaca bağlıysa (j < i) çarpma yerine toplam alınır: 0 + 1 + ... + (n−1) = n(n−1)/2, yani O(n²).

Dördüncü kural en çok hata yapılan yerdir. Bağımlı döngü bazen n²'den küçük çıkar: alıştırma 3 ve 7'de göreceksin.

Özyineleme: Doğrusal, İkili ve Böl-Yönet

Özyinelemeli kodda iki şeyi sorarız: kaç çağrı yapılıyor ve her çağrı kendi içinde ne kadar iş yapıyor?

// Doğrusal özyineleme: n çağrı, her biri O(1) -> O(n)
static long SumTo(int n) => n == 0 ? 0 : n + SumTo(n - 1);

// Böl-yönet: iki yarım problem + O(n) birleştirme
static void MergeSort(int[] a, int left, int right)
{
    if (left >= right) return;
    int mid = (left + right) / 2;
    MergeSort(a, left, mid);       // T(n/2)
    MergeSort(a, mid + 1, right);  // T(n/2)
    Merge(a, left, mid, right);    // O(n)
}

SumTo için T(n) = T(n−1) + O(1): zincir n halka uzunluğundadır, sonuç O(n). Yukarıdaki Fib ikili özyinelemedir: T(n) = T(n−1) + T(n−2) + O(1). Çağrı ağacı her seviyede en fazla ikiye katlanır ve derinliği n'dir, yani O(2ⁿ) üst sınırı geçerlidir (sıkı sınır yaklaşık 1,618ⁿ'dir; sınavlarda çoğunlukla O(2ⁿ) kabul edilir).

Merge sort'ta T(n) = 2T(n/2) + O(n). Ağır matematik olmadan şöyle düşün: en üst seviyede birleştirme n iş yapar. Bir alt seviyede n/2 boyutlu iki parça var, toplam yine n. Her seviyede toplam iş n'dir ve parçalar 1 elemana inene kadar log₂ n seviye oluşur. Sonuç: n × log n = O(n log n). Merge metodunun kendisi sıralama yazısında.

Bu tip denklemleri ezbere çözen araç Master teoremidir: T(n) = a·T(n/b) + f(n) biçiminde, f(n) ile n^(log_b a) karşılaştırılır. Merge sort'ta a = 2, b = 2 olduğundan n^(log₂ 2) = n; f(n) = Θ(n) bununla aynı mertebede, yani ikinci durum geçerli ve T(n) = Θ(n log n). Özyinelemeli binary search'te a = 1, b = 2, f(n) = Θ(1): n^(log₂ 1) = 1, yine ikinci durum, T(n) = Θ(log n).

Bellek (Alan) Karmaşıklığı

Aynı notasyon ek bellek için de kullanılır; girdinin kendisi genelde sayılmaz. Atlanan nokta özyinelemedir: her aktif çağrı yığında yer tutar. SumTo(n) tek değişken kullanıyor gibi görünür ama n iç içe çağrı yüzünden O(n) bellek harcar ve büyük n'de StackOverflowException ile çöker. Aynı toplamı döngüyle yazarsan bellek O(1)'e iner. Merge sort O(n) yardımcı dizi kullanır; Fib(n) üstel sürede çalışsa da aynı anda en fazla n çağrı aktif olduğundan belleği O(n)'dir.

Alıştırmalar: Bu Kodun Karmaşıklığı Nedir?

Önce kendin çöz, sonra çözüme bak.

// 1
for (int i = 0; i < n; i++)
    for (int j = 0; j < i; j++)
        count++;

// 2
for (int i = 1; i < n; i *= 2)
    for (int j = 0; j < n; j++)
        count++;

// 3
for (int i = n; i > 0; i /= 2)
    for (int j = 0; j < i; j++)
        count++;

// 4
for (int i = 0; i < n; i++) count++;
for (int j = 0; j < m; j++) count++;
for (int k = 0; k < n; k++)
    for (int t = 0; t < 100; t++)
        count++;

// 5
int s = 0;
while (s * s < n) s++;

// 6
static int F(int n)
{
    if (n <= 0) return 1;
    return F(n - 1) + F(n - 1);
}

// 7
for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j += i)
        count++;

// 8
static int Search(int[] a, int target, int low, int high)
{
    if (low > high) return -1;
    int mid = low + (high - low) / 2;
    if (a[mid] == target) return mid;
    return a[mid] < target
        ? Search(a, target, mid + 1, high)
        : Search(a, target, low, mid - 1);
}

Çözümler:

1. İç döngü i tur atar: 0 + 1 + ... + (n−1) = n(n−1)/2. O(n²). n = 16 için tam 120 tur.
2. Dış döngü log₂ n tur, iç döngü her seferinde n tur: O(n log n). n = 16 için 4 × 16 = 64.
3. İç döngü dıştakine bağlı: n + n/2 + n/4 + ... + 1 < 2n. O(n). "Dışta log n, içte n, o zaman n log n" demek buradaki tuzaktır; n = 1024 için sayaç 2047 çıkar, 10.240 değil.
4. n + m + 100n. Sabit 100 atılır, n ve m bağımsız girdiler olduğu için ikisi de kalır: O(n + m).
5. s, √n'e ulaşınca döngü biter: O(√n).
6. Her çağrı iki çağrı yapar, derinlik n: toplam 2ⁿ⁺¹ − 1 çağrı, O(2ⁿ) zaman. Bellek O(n)'dir çünkü aynı anda yalnızca bir dal aktiftir. 2 * F(n - 1) yazılsaydı aynı sonuç O(n) zamanda bulunurdu.
7. İç döngü yaklaşık n/i tur atar: n/1 + n/2 + ... + n/n = n × (1 + 1/2 + ... + 1/n). Parantez içi harmonik seridir ve yaklaşık ln n'dir: O(n log n).
8. Her çağrıda aralık yarılanır: T(n) = T(n/2) + O(1), O(log n) zaman. Özyinelemeli sürümde bellek de O(log n)'dir; yukarıdaki döngülü BinarySearch aynı işi O(1) bellekle yapar.

Küçük Bir Senaryo: Tekrarlı Eleman Kontrolü

Bir kayıt formunda gelen numara listesinde tekrar var mı diye bakman gerektiğini düşün. İlk akla gelen çözüm her çifti karşılaştırmaktır; ikincisi görülenleri bir HashSet içinde tutmaktır.

static bool HasDuplicateSlow(int[] a)
{
    for (int i = 0; i < a.Length; i++)
        for (int j = i + 1; j < a.Length; j++)
            if (a[i] == a[j]) return true;
    return false;
}

static bool HasDuplicateFast(int[] a)
{
    var seen = new HashSet<int>();
    foreach (int x in a)
        if (!seen.Add(x)) return true; // Add, eleman zaten varsa false döner
    return false;
}

İlki O(n²) zaman ve O(1) bellek, ikincisi ortalamada O(n) zaman ve O(n) bellek kullanır. Bu tipik bir zaman-bellek takasıdır: hızı, fazladan bellekle satın alıyorsun. İki sürümün en iyi durumu aynıdır (ilk iki eleman eşitse hemen dönerler); fark en kötü durumda, yani hiç tekrar yokken ortaya çıkar.

Ne Zaman Kullanılır, Ne Zaman Kullanılmaz?

Big O, girdi büyüyebildiğinde ve iki yaklaşım arasında seçim yaparken işe yarar: n milyonlara çıkabiliyorsa O(n²) ile O(n log n) arasındaki fark, kodun çalışıp çalışmaması arasındaki farktır. Veri yapısı seçimi de aynı analize dayanır; örneğin bir binary search tree dengeli kaldığında O(log n), bozulduğunda O(n) arama yapar.

Tek başına yetmediği yerler de var. Küçük ve sınırlı n'de (on elemanlı bir menü listesi gibi) sabit çarpanlar belirleyicidir; O(n²) bir insertion sort, O(n log n) bir merge sort'tan hızlı çalışabilir. Aynı sınıftaki iki algoritmayı kıyaslarken de notasyon bir şey söylemez. Bu durumlarda alternatif, ölçmektir: Stopwatch ile ya da bir benchmark kütüphanesiyle gerçek veride süre al. Big O neyi ölçeceğini söyler, ölçümün yerini tutmaz.

Sık Yapılan Hatalar

1. Yanlış terimi atmak. O(n² + n log n) ifadesinde baskın terim n²'dir, n log n atılır. Ama O(n + m)'de m atılamaz: m ayrı bir girdidir ve n'den büyük olabilir. Benzer şekilde O(2n) ya da O(n/2) yazmak notasyon hatasıdır; ikisi de O(n)'dir. Logaritmanın tabanı da sabit çarpandır: O(log₂ n) ile O(log₁₀ n) aynı sınıftır.

2. En iyi durumu Ω ile karıştırmak. En iyi, ortalama ve en kötü durum girdinin türünü anlatır; O, Ω ve Θ ise seçilen durumun fonksiyonuna konan sınırın türünü. Insertion sort'un en iyi durumu Θ(n), en kötü durumu Θ(n²)'dir. "Insertion sort Ω(n)'dir" cümlesi doğrudur ama "en iyi durum" anlamına gelmez; her girdide en az n işlem yapıldığını söyler.

3. İki döngü görünce n² demek. Art arda iki döngü O(n)'dir. İç içe olsalar bile alıştırma 2, 3 ve 7'deki gibi sonuç n log n ya da n çıkabilir. Döngü saymak yerine iç gövdenin toplam kaç kez çalıştığını hesapla.

4. Gizli maliyeti görmemek. Döngü içinde çağrılan metot O(1) olmayabilir:

for (int i = 0; i < list.Count; i++)
    if (list.Contains(target - list[i])) return true; // Contains O(n) -> toplam O(n²)

List<T>.Contains doğrusal arama yapar; tek döngü görünen bu kod O(n²)'dir. HashSet<T> ile ortalamada O(n)'e iner.

Bu tür soruları kendi dersinin çıkmış sınavlarıyla çalışmak istersen sınav destek sayfasına bakabilirsin.

Sık Sorulan Sorular

Big O her zaman en kötü durumu mu gösterir?

Hayır. Big O bir üst sınır notasyonudur ve en iyi, ortalama ya da en kötü durumun hepsine uygulanabilir. Pratikte çoğunlukla en kötü durum için kullanıldığından ikisi karıştırılır.

O(n log n) içindeki logaritmanın tabanı nedir?

Yarıya bölme işlemlerinden geldiği için genellikle 2'dir, ama notasyon açısından fark etmez. Farklı tabanlar birbirinin sabit katıdır ve sabit çarpanlar Big O'da atılır.

Master teoremi her özyinelemeye uygulanır mı?

Hayır, yalnızca T(n) = a·T(n/b) + f(n) biçimindeki böl-yönet denklemlerine uygulanır. T(n) = T(n−1) + O(1) ya da Fibonacci gibi problemi çıkarmayla küçülten denklemlerde çağrı zinciri ya da özyineleme ağacı yöntemi kullanılır.

Zaman karmaşıklığı mı, bellek karmaşıklığı mı daha önemli?

Duruma bağlıdır. Sınavlarda ve çoğu uygulamada önce zaman sorulur, ama bellek sınırlıysa ya da özyineleme derinliği büyükse bellek belirleyici olur. İyi bir cevap ikisini de belirtir.