Big-O Notasyonu

Büyük O Notasyonu (Big-O Notation), bilgisayar bilimlerinde algoritmaların verimliliğini ölçmek için kullanılan temel asimptotik analiz araçlarından biridir. Bu notasyon, bir algoritmanın çalışma süresinin veya bellek kullanımının, girdi boyutuna bağlı olarak ne şekilde büyüdüğünü teorik bir çerçevede ifade eder. Big-O, belirli bir fonksiyonun üst sınırını tanımlamak amacıyla kullanılır ve bu yönüyle algoritmaların karmaşıklık analizinde temel bir ölçü birimi hâline gelmiştir.

Terim, Almanca Ordnung (sıra, düzen) kelimesinden türetilmiş olup 1894 yılında Paul Bachmann tarafından “Analytische Zahlentheorie” isimli eserinde tanıtılmıştır. Donald Knuth’un bu kavramı sistematik olarak bilgisayar bilimine kazandırmasıyla modern algoritma analizinin vazgeçilmez bir unsuru olmuştur.

Bir fonksiyon f(n), başka bir fonksiyon g(n) cinsinden Büyük O notasyonu ile ifade edildiğinde, f(n) = O(g(n)) şeklinde gösterilir. Bu ifade, f(n) fonksiyonunun g(n) fonksiyonunun sabit bir katından büyük olamayacağını söyler. Daha resmi tanımıyla:

Tanım: f(n) = O(g(n)) ise ve ancak ancak pozitif sabitler c ve k var ise:

$0\le f(n)\le c\ast g(n),\forall n\ge k$

Burada c ve k sabitleri sabittir ve n'ye bağlı değildir. Bu tanım, Big-O kavramının temel amacını ortaya koyar: Algoritmanın en kötü durumda nasıl davrandığını anlamak.

Büyük O Notasyonu’nun temel işlevi, algoritmaların çalışma süresi veya bellek gereksiniminin giriş boyutuna bağlı olarak nasıl büyüdüğünü göstermektir. Bu bağlamda, asimptotik üst sınır kavramı, bir algoritmanın performansının en kötü durumda alabileceği maksimum değeri temsil eder. Bu, algoritmanın pratikte her zaman bu süreyi harcayacağı anlamına gelmez; ancak en olumsuz senaryoda bile belirli bir üst sınırın aşılmayacağını garanti eder.

Formel olarak, bir fonksiyon f(n) için asimptotik üst sınır şöyle ifade edilir:

$f(n)=O(g(n))=>\exists c>0,\exists k\ge 0,\forall n\ge k:0\le f(n)\le c\ast g(n)$

Buradaki g(n), karşılaştırma fonksiyonu olup, f(n) fonksiyonunun büyüme hızını kontrol altında tutacak referans değeridir. Sabit c ve başlangıç noktası k, yalnızca f ve g fonksiyonlarına bağlıdır, n’ye bağlı değildir. Böylece analiz, donanıma, dile veya derleyiciye bağlı olmaksızın algoritmanın temel büyüme eğilimini ortaya koyar.

Big-O notasyonunun kuramsal gücü, bazı temel özellikleri sayesinde sağlam temellere oturur:

Her fonksiyon kendisiyle aynı sınıfa dahildir:

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

Büyüme sınıfları zincirleme aktarılabilir:

$f(n)=O(g(n)),g(n)=O(h(n))=>f(n)=O(h(n))$

Sabitler asimptotik büyümeyi etkilemez:

$f(n)=O(g(n))=>c\ast f(n)=O(g(n)),c>0$

$f(n)=O(h(n)),g(n)=O(k(n))⟹f(n)+g(n)=O(maxh(n),k(n))$

$f(n)=O(h(n)),g(n)=O(k(n))⟹f(n)\cdot g(n)=O(h(n)\cdot k(n))$

Bir algoritmanın karmaşıklığı genelde giriş boyutu n cinsinden ifade edilir. Bazı yaygın sınıflar şunlardır:

• O(1): Sabit zaman — örn. bir diziye indeksle erişim.
• O(log n): Logaritmik — örn. binary search.
• O(n): Doğrusal — örn. lineer arama.
• O(n log n): Log-lineer — örn. merge sort.
• O(n²): Karesel — örn. bubble sort.
• O(2ⁿ): Üssel — örn. alt küme üretme.
• O(n!): Faktöriyel — örn. tüm permütasyonları üretme.

Big-O Notasyonu, hesaplamalı karmaşıklık teorisinin de temelidir. P ve NP sınıfları, polinom zamanda çözülebilirlik (O(n^c)) veya üssel/faktöriyel zaman (O(2ⁿ), O(n!)) gibi sınıflar üzerinden tanımlanır.

Bir algoritmanın polinom zamanda çalışması (O(n^k)) genelde uygulanabilirlik ölçütü olarak kabul edilir. Aksi hâlde problem NP-Zor ya da NP-Tam olarak sınıflandırılabilir.

Kaynak metinlerinde Big-O ve Big-Θ kavramlarının otomata kuramındaki özel kullanımları da tartışılmıştır. Bazı ağırlıklı otomatlarda, bir durumu Big-O cinsinden test etmek, Big-Θ’ya dönüştürülebilir. Cook ve Karp indirgemeleri, bir karar probleminin başka bir problem üzerinden çözülebileceğini gösterir.

Ayrıca “Eventually Big-O” kavramı, sonsuz uzunlukta sözcüklerde Big-O sınırlarının sağlanması gerektiğini belirtir. Bazı semiringlerde (örneğin tropikal semiring) bu tür kapsama problemleri karara bağlanabilirken, bazılarında kararsız (undecidable) olabilir.$0\le f(n)\le c\ast g(n),\forall n\ge k$