Big O gösteriminin görsel bir tanıtımı

(samwho.dev)

2 puan yazan GN⁺ 2025-08-26 | Henüz yorum yok. | WhatsApp'ta paylaş

Big O gösterimi, bir fonksiyonun performansını girdi boyutu değiştikçe büyüme biçimiyle ifade eder
Yazıda başlıca sabit, logaritmik, doğrusal ve karesel Big O türleri örneklerle açıklanır
Veri yapısı ve algoritmaya göre zaman karmaşıklığı değişir; dizi sıralama, arama gibi işlemlerde bu fark görülür
Gerçek kod performansını iyileştirmek için uygun veri yapısını seçmek ve döngüler içindeki gereksiz işlemleri kaldırmak kritik önemdedir
Big O, her zaman girdi ile çalışma süresi arasındaki ilişkiyi en sade haliyle gösterir; performans iyileştirmelerinde kodu doğrudan ölçmek önemlidir

Big O gösterimine genel bakış

Big O gösterimi, süreyi doğrudan ölçmek yerine girdi boyutuna (n) göre çalışma süresinin nasıl büyüdüğünü açıklayan bir yöntemdir
Bir fonksiyonun çalışma süresini girdi boyutuna göre sınıflandırır; en yaygın incelenen biçimler sabit (O(1)), logaritmik (O(log n)), doğrusal (O(n)) ve karesel (O(n²)) yapıdadır
Bu yazı, yeni başlayanların da anlayabilmesi için her bir kategoriyi kavramsal anlatım, görsel örnekler ve gerçek kod örnekleriyle açıklar

Yineleme (Iterating) ve doğrusal algoritmalar

sum(n) fonksiyonu, 1'den n'e kadar toplama yapan bir yineleme yapısının örneğidir; girdi değeri n büyüdükçe çalışma süresi de doğru orantılı olarak artar
Gerçekte sum(1e9) yaklaşık 1 saniye, sum(2e9) ise yaklaşık 2 saniye sürer; yani duvar saati süresi (wall-clock time) O(n) düzeninde büyür
Zaman karmaşıklığı, fonksiyon girdisi ile çalışma süresi arasındaki ilişkidir ve bu ilişki Big O gösterimiyle ifade edilir (O(n) — n ile orantılı)
Yineleme yerine matematiksel formül kullanan sum(n) = (n*(n+1))/2 yaklaşımında çalışma süresi girdi değeri n'den bağımsız olarak sabittir
Bu tür fonksiyonlar sabit zaman karmaşıklığı O(1) olarak adlandırılır; ayırt edici özellikleri, girdi değişse de çalışma süresinin büyümemesidir

Big O gösteriminin sözdizimi

Big O'daki O harfi “Order (büyüme derecesi)” kavramından gelir ve yalnızca büyümenin biçimini gösterir
Mutlak çalışma süresini değil, girdiye göre büyümenin 'desenini' kısa ve öz şekilde ifade eder
Örneğin bir O(n) fonksiyonu için 'O(2n)' ya da 'O(n+1)' gibi karmaşık yazımlar kullanılmaz; bunun yerine en sade terim seçilir

Girdi yapısını kullanarak süreyi kısaltma

sum(n) formülü örneğinde olduğu gibi, algoritmayı iyileştirerek zaman karmaşıklığını O(n)'den O(1)'e dönüştürmek mümkündür
Ancak sabit zaman karmaşıklığı her zaman mutlak olarak daha hızlı olmak zorunda değildir; toplam çalışma süresi, yapılan işlemin türüne göre değişebilir
Bir O(n) algoritması belirli girdilerde O(1)'den daha hızlı olabilir, ancak girdi boyutu büyüdükçe O(1) yaklaşımı sonunda üstün gelir

Sıralama (Sorting) ve karesel (Quadratic) algoritmalar: Bubble Sort örneği

Bubble Sort, komşu değerleri tekrar tekrar yer değiştirerek diziyi sıralayan temel bir örnektir
Dizi zaten sıralıysa 1 tur yeterlidir (O(n)); ters sıralıysa n kez dolaşmak gerekir → en kötü durumda toplam işlem sayısı n² olur
O(n²) algoritmalar, girdi büyüdükçe çalışma süresinin karesel biçimde ciddi şekilde arttığı yapılardır
Pratikte Big O her zaman en kötü durum (worst-case) temel alınarak kullanılır (ancak bazen ortalama/en iyi durum da ayrıca belirtilir)
Dizinin başlangıç durumuna göre tur sayısı azalabilir, ancak en kötü durum dikkate alındığı için her zaman karesel zaman karmaşıklığıyla sınıflandırılır

Arama (Searching) ve logaritmik algoritmalar: Binary Search örneği

Binary Search, sıralı bir aralıkta orta noktayı tahmin eder ve her adımda aday alanın yarısını eler
Örneğin 1 ile 100 arasındaki belirli bir sayıyı bulmak için en fazla 7 deneme gerekir; 1 ile 1 milyar arasında bile 31'den az denemeyle sonuca ulaşılabilir
Her adımda aday listenin yarıya inmesi nedeniyle çalışma süresi O(log n) yani logaritmik zaman karmaşıklığıdır
Logaritmik algoritmalar, n büyüdüğünde bile çok yavaş artar; bu da onları doğrusal veya karesel algoritmalara göre çok daha verimli kılar
Grafikte karşılaştırıldığında log n, n ve n² arasındaki büyüme farkı çok net biçimde görülür

Gerçek uygulama: zaman karmaşıklığını iyileştirme ipuçları

Listede öğe bulma

Temel olarak bir dizide değer arayan fonksiyon O(n) düzeyindedir
Sık arama yapılıyorsa Set gibi bir veri yapısı kullanılarak bu işlem O(1) düzeyine çıkarılabilir
Ancak new Set(array) ile dönüştürme işleminin kendisi O(n) olduğundan, bu yaklaşım yalnızca sık sorgulama durumlarında uygundur (dönüştürme maliyeti hesaba katılmalıdır)
Örneğin items.has("banana") sabit zaman karmaşıklığı sağlar

İndeks kullanan döngüler yazma

Aşağıdaki gibi, döngü içinde .indexOf kullanan kodlar sıkça performans sorununa yol açar

function buildList(items) {
  const output = [];
  for (const item of items) {
    const index = items.indexOf(item);
    output.push(`Item ${index + 1}: ${item}`);
  }
  return output.join("\n");
}

.indexOf, döngü içinde O(n) işlem olduğundan toplamda O(n^2) desenine dönüşür

İndeks tabanlı döngü ya da forEach((item, index) => ...) kullanıldığında bu yapı O(n) düzeyine iyileştirilebilir

function buildList(items) {
  const output = [];
  for (let i = 0; i < items.length; i++) {
    output.push(`Item ${i + 1}: ${items[i]}`);
  }
  return output.join("\n");
}

Memoization kullanımı

Faktöriyel gibi tekrar tekrar çağrıldığında aynı hesapları üreten yapılarda sonuç önbellekleme (Map kullanımı) uygulanarak performans artırılabilir
Map üzerindeki sorgulama O(1) olduğundan gereksiz yeniden hesaplamalar en aza iner

Ancak önbellekleme daha çok ortalama süreyi iyileştirir; en kötü zaman karmaşıklığı değişmese bile verimli bir performans artışı sağlayabilir

const cache = new Map();
function factorial(n) {
  if (cache.has(n)) {
    return cache.get(n);
  }
  if (n === 0) {
    return 1;
  }
  const result = n * factorial(n - 1);
  cache.set(n, result);
  return result;
}

Performans değerlendirmesi ve sonuç

Kod performansını iyileştirirken, teorik zaman karmaşıklığının yanı sıra doğrudan çalıştırma testleriyle gerçek iyileşmenin olup olmadığını doğrulamak gerekir
Big O, girdi ile çalışma süresi arasındaki ilişkiyi ve büyüme desenini en özlü biçimde ifade eder
Doğru algoritma seçimi ve veri yapısı optimizasyonu ile kod verimliliği en üst düzeye çıkarılabilir

Kısa özet

Big O gösterimi, fonksiyon girdisi ile çalışma süresi arasındaki ilişkiyi ifade eder
Başlıca performans düzeyleri: O(1) (sabit), O(log n) (logaritmik), O(n) (doğrusal), O(n^2) (karesel)
Verimli kod yazmak için uygun algoritma seçimi ve döngü optimizasyonu önemlidir
Gerçek performans, iyileştirmenin etkisini doğrulamak için doğrudan ölçülmelidir
Büyüme desenlerini karşılaştıran grafikler, zaman karmaşıklığı özelliklerini tek bakışta anlamayı sağlar