Karmaşıklık analizi: Big-O, Ω, Θ

Veri yapıları dersinin ilk sorusu hep aynı: bu kod ne kadar hızlı? Saniye ile ölçmeyiz, çünkü saniye bilgisayara göre değişir. Onun yerine girdinin boyutu n büyüdükçe yapılan işlem sayısının nasıl büyüdüğüne bakarız. Sınavda bir kod parçası verilir ve “What is the time complexity?” diye sorulur. Cevap tek satır ama gerekçesi döngüleri doğru saymaya dayanır.

Altın kurallar:

1. Sabitleri at. 3n ile n aynı sınıftadır: O(n).
2. Baskın terimi tut. n² + 1000n için cevap O(n²).
3. Art arda döngüler toplanır, iç içe döngüler çarpılır.
4. Sayaç ikiye katlanıyor ya da yarıya iniyorsa tur sayısı log n’dir.
5. İç döngünün sınırına bak. n’ye bağlı değilse iç döngü sabittir.

Algoritma ve çalışma süresi

Algoritma (algorithm), bir problemi çözen sonlu adımlar dizisidir. Veri yapısı (data structure) ise verinin bellekte nasıl düzenlendiğidir: dizi, bağlı liste, yığın, kuyruk. Aynı problemi farklı veri yapılarıyla çözebilirsin ve hız ciddi şekilde değişebilir. Bu ders boyunca her yapı için “ekleme kaç adım, silme kaç adım, arama kaç adım” sorusunu soracağız.

Çalışma süresini (running time) n’nin fonksiyonu olarak yazarız: T(n). Bir dizinin elemanlarını toplayan şu metodu düşün:

int sum = 0;                    // 1 işlem
for (int i = 0; i < n; i++) {   // her turda 1 karşılaştırma
    sum += a[i];                // her turda 1 toplama
}
return sum;                     // 1 işlem

Kabaca T(n) = 2n + 2 işlem. n = 10 için 22, n = 100 için 202. Burada tam sayının önemi yok. Önemli olan: n on katına çıkınca iş de yaklaşık on katına çıkıyor. Bu doğrusal (linear) büyümedir ve O(n) yazılır.

Big-O, Big-Omega, Big-Theta

Üç gösterim var ve üçü de “büyük n için fonksiyon hangi hızla büyüyor” sorusunu cevaplar.

Resmi tanım: Bir $c > 0$ sabiti ve bir $n_0$ varsa, öyle ki her $n \ge n_0$ için $T(n) \le c \cdot f(n)$ ise $T(n) = O(f(n))$.

Örnek: $T(n) = 3n + 5$. $c = 4$, $n_0 = 5$ seçersen $n \ge 5$ için $3n + 5 \le 4n$ olur. O halde $T(n) = O(n)$. Aynı zamanda $3n + 5 \ge 3n$ olduğundan $\Omega(n)$, ikisi birden olduğundan $\Theta(n)$.

TUZAK · Big-O sadece üst sınırdır. $3n + 5 = O(n^2)$ ifadesi de matematiksel olarak doğrudur, çünkü n² daha hızlı büyür. Ama sınavda “tightest bound” (en sıkı sınır) istenir. Cevabın O(n) olmalı.

Pratikte sınavlarda Big-O sorulur ve en sıkı cevap beklenir. Big-Theta ile aynı şeyi yazıyorsun gibi düşünebilirsin.

En iyi, en kötü, ortalama durum

Bazı algoritmalarda süre girdinin içeriğine de bağlıdır. Dizide doğrusal arama (linear search) yaparken aradığın eleman ilk sıradaysa 1 karşılaştırma yeter (best case, O(1)). Hiç yoksa n karşılaştırma gerekir (worst case, O(n)). Aksi belirtilmedikçe Big-O en kötü durum (worst case) için verilir.

Yaygın büyüme hızları

Sıralama: $1 < \log n < \sqrt{n} < n < n\log n < n^2 < n^3 < 2^n < n!$

Bilgisayar bilimlerinde log tabanı belirtilmezse 2’dir. Big-O içinde taban fark etmez, çünkü $\log_2 n$ ile $\log_{10} n$ arasında sadece sabit bir çarpan var.

İPUCU · Süre tahmini. “O(n²) algoritma n = 1000 için 2 saniye sürüyor, n = 4000 için ne kadar?” sorusunda oranı kullan: n 4 kat → süre 4² = 16 kat → 32 saniye. O(n) olsaydı 4 kat (8 saniye), O(n³) olsaydı 64 kat olurdu.

Döngülerde işlem sayma

Sınavın gerçek konusu bu. Her döngü için “kaç kez döner?” diye sor, sonra birleştir.

Tek döngü

for (int i = 0; i < n; i++)      // n tur → O(n)
    count++;

for (int i = 0; i < n; i += 3)   // n/3 tur → hâlâ O(n)
    count++;

Adım büyüklüğü sabit olduğu sürece (1, 2, 3…) döngü doğrusaldır.

Çarpan / bölen döngü

for (int i = 1; i < n; i *= 2)   // 1, 2, 4, 8, ... → log n tur
    count++;

Kaç kez ikiye katlarsan n’yi geçersin? $2^k \ge n$ ise $k = \log_2 n$. Aynısı i /= 2 ile aşağı inen döngü için de geçerli. n = 16 için i: 16, 8, 4, 2, 1. Beş tur, yani $\log_2 16 + 1$.

Sayaçla doğrulama (n iki katına çıkıyor):

i *= 2 döngüsü:   n=1000 → 10 tur   n=2000 → 11   n=4000 → 12   n=8000 → 13

n iki katına çıkınca sadece bir tur ekleniyor. Logaritmik büyümenin işareti bu.

İç içe döngüler

for (int i = 0; i < n; i++)
    for (int j = 0; j < n; j++)
        count++;                 // n · n = n² → O(n²)

İç döngünün sınırı dış döngünün değişkenine bağlıysa toplamı açık yaz:

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

i = 0 → iç döngü 0 kez
i = 1 → 1 kez
i = 2 → 2 kez
...
i = n-1 → n-1 kez
Toplam = 0 + 1 + ... + (n-1) = n(n-1)/2
n = 10 → 45

$\frac{n(n-1)}{2} = \frac{n^2}{2} - \frac{n}{2}$. Baskın terim $\frac{n^2}{2}$, sabiti at: O(n²). Yarısı kadar iş yapıyor ama sınıfı değişmiyor.

Karışık: doğrusal × logaritmik

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

Toplam n log n. Sayaç sonuçları:

n=1000 → 10000   n=2000 → 22000 (x2.20)   n=4000 → 48000 (x2.18)   n=8000 → 104000 (x2.17)

O(n) olsaydı oran tam 2 olurdu, O(n²) olsaydı 4. 2’nin biraz üstü: n log n.

Art arda döngüler

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

Toplam $n + n^2$, baskın terim n²: O(n²). Toplanır, çarpılmaz.

Bağımlı ama logaritmik dış döngü

Zor bir örnek: dış döngü katlanıyor, iç döngü i kadar dönüyor.

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

İç döngü sırasıyla 1, 2, 4, …, n kez döner. Toplam $1 + 2 + 4 + \dots + n = 2n - 1$. Yani O(n). n = 16 için 31 tur, n = 1024 için 2047 tur. “İki döngü var, n log n’dir” diye refleksle cevap verme; topla.

Adım adım çözüm kalıbı

Sınavda her kod parçası için şunu yap:

1. En içteki ifade kaç kez çalışıyor? Her döngü için tur sayısını yaz.
2. İç içe ise tur sayılarını çarp (iç döngü dışa bağlıysa toplamı aç).
3. Art arda ise topla.
4. Baskın terimi al, sabitleri at.
5. Emin değilsen n = 8 veya n = 16 için elle say, sonra n'yi iki katına çıkar ve oranı kontrol et.

Beşinci adım hayat kurtarır. n = 8 → 24 işlem, n = 16 → 64 işlem gibi bir sonuç bulduysan oran yaklaşık 2.7, bu n log n’ye işaret eder (8·3 = 24, 16·4 = 64).

Sık yapılan hatalar

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

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

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

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

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

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

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

for (int i = 1; i * i <= n; i++)
    count++;

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