Big O Gösterimi — Zaman Karmaşıklığının Basit Anlatımı

Big O gösterimi, girdi boyutu arttıkça bir algoritmanın çalışma süresinin veya bellek kullanımının ne kadar hızlı artabileceğini anlatır. “Problem çok daha büyürse ne olur?” diye soruyorsanız, bunu yanıtlamanın standart yolu Big O'dur.

Bu yüzden doğrusal aramanın $O(n)$, ikili aramanın ise $O(\log n)$ olduğu söylenir. Amaç, tek bir makinede tam olarak kaç milisaniye süreceğini tahmin etmek değildir. Amaç, büyüme biçimlerini karşılaştırmaktır.

Big O Ne Anlama Gelir?

Bir algoritma, boyutu $n$ olan bir girdi için $T(n)$ kadar zaman alıyorsa,

$$T(n) = O(f(n))$$

ifadesi, bazı $C > 0$ ve $n_0$ sabitleri için

$$T(n) \le C f(n) \quad \text{for all } n \ge n_0$$

anlamına gelir.

Bu, Big O'nun yeterince büyük girdiler için büyüme hakkında bir üst sınır ifadesi olduğunu söyler.

Daha sade bir dille: $n$ yeterince büyük olduğunda, çalışma süresi $f(n)$'in sabit bir katından daha hızlı büyümez.

Big O Neden Kullanışlıdır?

Big O, algoritmaları makineden bağımsız biçimde karşılaştırmayı sağlar. Bir program bir dizüstü bilgisayarda diğerinden daha hızlı çalışabilir, ama büyüme eğilimi yine de önemlidir.

Bu eğilim özellikle girdi boyutu çok değiştiğinde önem kazanır. $100$ öğe için uygun olan bir algoritma, büyüme oranı kötüyse $10^6$ öğe için kullanışsız hale gelebilir.

Yaygın Zaman Karmaşıklıkları Kısaca

• $O(1)$: $n$ büyüse bile yapılan iş sınırlı kalır.
• $O(\log n)$: yapılan iş yavaş büyür; bu genelde problem boyutu tekrar tekrar küçültüldüğünde görülür.
• $O(n)$: yapılan iş, girdi boyutuyla yaklaşık orantılı olarak artar.
• $O(n \log n)$: doğrusaldan biraz daha fazladır; verimli sıralama algoritmalarında yaygındır.
• $O(n^2)$: yapılan iş, girdi boyutunun karesi gibi büyür; bu da çoğu zaman aynı veri üzerinde iç içe döngülerden kaynaklanır.

Bu etiketler tam hızı değil, büyümeyi karşılaştırır. Sabit çarpanları büyükse, $O(n)$ bir algoritma küçük girdilerde yine de $O(n^2)$ bir algoritmadan daha yavaş olabilir.

Çözümlü Örnek: Doğrusal Arama Neden $O(n)$'dir?

Bir hedef değeri bulmak için bir listeyi soldan sağa taradığınızı düşünün. En kötü durumda hedef ya listede yoktur ya da en sondadır; bu yüzden her öğeyi bir kez kontrol etmeniz gerekebilir.

Liste $n$ öğeden oluşuyorsa, kontrol sayısı en fazla $n$ olabilir. Bu yüzden en kötü durumdaki süre

$$O(n)$$

olur.

Buradan çıkarılacak yararlı sonuç basittir: liste boyutu iki katına çıkarsa, en kötü durumdaki kontrol sayısı da yaklaşık iki katına çıkabilir. Big O'nun yakaladığı örüntü tam olarak budur.

Big O Neleri Dışarıda Bırakır?

Big O, büyük girdilerdeki büyümeyi karşılaştırırken sabit çarpanları ve düşük dereceli terimleri bilerek göz ardı eder.

Örneğin,

$$T(n) = 3n + 2$$

ise, $T(n)$ yine de $O(n)$'dir. $3$ sabiti ve fazladan $2$, tam süre hesabında önemlidir; ama ana büyüme biçimini değiştirmez.

Bu, sabitlerin pratikte hiç önemli olmadığı anlamına gelmez. Sadece Big O'nun daha dar bir soruya cevap verdiği anlamına gelir: $n$ büyüdüğünde maliyet nasıl ölçeklenir?

Big O ile İlgili Yaygın Hatalar

Hata 1: Big O'yu tam çalışma süresi sanmak

$O(n)$, çalışma süresinin tam olarak $n$ adım olduğu anlamına gelmez. Bu, $n$ yeterince büyük olduğunda büyümenin $n$'in sabit bir katıyla yukarıdan sınırlandığı anlamına gelir.

Hata 2: Büyük-$n$ koşulunu unutmak

Biçimsel tanımın yalnızca tüm $n \ge n_0$ için geçerli olması gerekir. Big O, her küçük girdiyle değil, asimptotik davranışla ilgilidir.

Hata 3: Big O'nun her zaman tipik çalışma süresini anlattığını sanmak

Algoritma tartışmalarında Big O çoğu zaman en kötü durum süresini anlatır, ama bu bağlama bağlı bir kullanım alışkanlığıdır. Ortalama durum ve en iyi durum karmaşıklığı farklı sorulardır ve açıkça belirtilmelidir.

Hata 4: Algoritmaları yalnızca Big O ile karşılaştırmak

Big O önemlidir, ancak gerçek sistemlerde bellek kullanımı, uygulama maliyeti ve sabit çarpanlar da çok önemli olabilir.

Big O Gösterimini Nerede Görürsünüz?

Big O; bilgisayar biliminde, ayrık matematikte ve performans analizinde karşınıza çıkar. Özellikle arama, sıralama, grafik dolaşma ve dinamik programlama algoritmalarını karşılaştırırken çok yararlıdır.

Daha genel olarak, yalnızca sabit bir boyuttaki davranışla değil, bir sürecin nasıl ölçeklendiğiyle ilgilendiğiniz her yerde kullanılır.

Benzer Bir Örneği Siz Deneyin

$n \times n$ boyutunda bir ızgara üzerinde çalışan basit bir iç içe döngü düşünün. İçteki işlemin kaç kez çalıştığını sayın. Toplam iş $n^2$ gibi büyüyorsa, aynı veri üzerinde tekrarlanan döngülerin neden çoğu zaman $O(n^2)$ davranışına yol açtığına dair somut bir örneğiniz olur.