Big-O Gösterimi nedir?
Big-O Notation (Büyük O Gösterimi)
Bir algoritmanın çalışma süresinin veya bellek kullanımının girdi büyüdükçe nasıl arttığını ifade eden gösterim.
Big-O gösterimi, bir algoritmanın girdi boyutu (n) büyüdükçe ne kadar yavaşlayacağını veya ne kadar fazla bellek kullanacağını kabaca ifade eder. Saniye cinsinden kesin bir süre vermez; büyüme hızını anlatır. Genellikle en kötü durum (worst case) için kullanılır ve sabit çarpanlar ile küçük terimler göz ardı edilir.
Sık karşılaşılan karmaşıklıklar hızlıdan yavaşa şöyledir: O(1) sabit zaman (dizide indeksle erişim), O(log n) logaritmik (sıralı dizide ikili arama), O(n) doğrusal (listeyi baştan sona tarama), O(n log n) (merge sort gibi verimli sıralama algoritmaları), O(n²) karesel (iç içe iki döngü) ve O(2ⁿ) üstel (naif özyinelemeli Fibonacci).
Küçük girdilerde fark hissedilmez, ancak veri büyüdükçe belirleyici olur. Örneğin bir milyon elemanlı sıralı listede doğrusal arama en kötü durumda bir milyon karşılaştırma yaparken, ikili arama yaklaşık 20 karşılaştırmada sonuca ulaşır. Big-O, yazılım mülakatlarında da en sık sorulan konulardandır.
Örnek: O(n) ve O(log n) arama karşılaştırması
def dogrusal_ara(liste, hedef): # O(n)
for i, x in enumerate(liste):
if x == hedef:
return i
return -1
def ikili_ara(liste, hedef): # O(log n), liste sıralı olmalı
lo, hi = 0, len(liste) - 1
while lo <= hi:
mid = (lo + hi) // 2
if liste[mid] == hedef: return mid
if liste[mid] < hedef: lo = mid + 1
else: hi = mid - 1
return -1İpuçları
- İç içe döngü gördüğünüzde O(n²) olabileceğini düşünün; çoğu zaman bir sözlük/küme ile O(n)'e indirilebilir.
- Big-O sadece zaman için değil, bellek (alan karmaşıklığı) için de kullanılır.
