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

(samwho.dev)

2 puan yazan GN⁺ 2025-08-26 | 1 yorum | 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

1 yorum

GN⁺ 2025-08-26

Hacker News görüşleri

Bu yazı ve HN yorumları da Big O Notation’ı açıklama, gerçek kullanımını ve teknik ayrıntılarını tartışma geleneğini sürdürmeye devam ediyor. Bakmaya değer örnekler olarak bu açıklama yazısı ve uzman tavrı üzerine yazı var
- Önceki yazının yorumlarına bakınca Pyon adlı kullanıcının zehirleyici ve esnek olmayan bir tavır sergilediği görülüyordu. Ama Ned’in karşı çıkışı da pek başarılı sayılmaz. Teknik ayrıntıları doğru düzgün açıklamadan sadece “belli ayrıntılar” deyip duruyormuş gibi hissettiriyor. Neden eleştirinin sadece laf olsun diye yapıldığını ve neden içeriğin kendisini de dışladığını açıklamaması da eksik kalmış. Ned çevrimiçi iletişim ve empati konusunda doğru bir yön gösteriyor. Yine de bir eğitimci olarak, o teknik noktanın neden aşırı ayrıntıcı ya da gereksiz bir itiraz olduğunu en az bir kez açıklamasını isterdim. Ned’in kendisinin sadece “on yıllardır bilmiyordum” demesi yeterli gelmiyor. Eski yorum dizisine tekrar bakınca Ned aslında oldukça diplomatik ve ciddi biçimde tartışmış. O yüzden blog yazısında bu analizin neden yer almadığını merak ediyorum. Kişisel olarak teknik ayrıntının ne olduğunu pek bilmiyorum ama bir kez olsun kısa bir özet açıklama görmek isterdim
- Ben eleştirel uzmana daha yakınım. Bloglarda karmaşık konuları öğretme girişimlerini görünce hep hayal kırıklığına uğramamın nedeni, çoğu zaman uzman olmayan kişilerin açıklama yaparken doğruluğu kaçırması. Sonuç olarak 1) yanlış içerikler internetin dört bir yanına kopyalanıp yapıştırılıyor, 2) okurlar blog düzeyindeki açıklamayla yetinip daha fazlasını öğrenmemeye yönelerek cehaletlerini pekiştiriyor. Bir de ayrıca sayfa düzenini sevmedim. ADHD ve zayıf hafıza deneyimime göre uygun biçimde bölümlere ayırma (alt başlık/kalın/vurgu rengi/madde işaretleri vb.) olmadan takip edemiyorum; bu yazı dümdüz bir metin duvarı gibi geldi. Ana fikri anlamak ne kadar uzun sürerse dikkatim o kadar çabuk dağılıyor. Simple Wikipedia’daki Big O açıklaması çok daha doğrudan. Buna karşılık asıl Wikipedia sayfasında matematik bir anda devreye giriyor; bakınca Big O’nun sanıldığından çok daha karmaşık bir konu olduğu görülüyor ve “basitleştirmek belki de iyi bir fikir olmayabilir” sonucuna varılıyor
- İkinci bağlantı Big-O hakkında değil ve böyle bir tavrı örnek almaya gerek yok
- Ned birkaç gün önce bana e-posta gönderdi, ben de memnuniyetle bu tartışmalara katkıda bulunuyorum
- Bu tür yazılarda asıl ders şu: yanlış ya da yanıltıcı açıklamalar varsa düzeltmeyi bırakmak değil, internette bazı “uzmanlar”ın sadece tartışmayı kazanmak istediğini görmek gerekir. Pyon’un tavrına bakınca oldukça saldırgan ve internet trolü gibiydi. Buradan asla “öyleyse teknik ayrıntılar önemli değil ve yanlış olmak sorun değil” sonucu çıkarılmamalı
O(1) pratikte bir hashing fonksiyonu kullanır; bu da basit değildir ama sabit miktarda işlem gerektirir. Veri çok azken O(n^2) gibi en kötü algoritma bile gerçek çalışma süresinde daha hızlı olabilir
- Doğru ama bunu fazla büyütmemek daha iyi. Gerçek dünyada insanlara n^2 olursa bilgisayarın durma noktasına geleceğini anlatmak bile zor. Üstelik bazı durumlarda mod gibi mükemmel bir hash fonksiyonu da kullanılabilir
Big-O’nun günümüzdeki öneminin eskisi kadar olmadığını hissediyorum. Modern donanım çoklu iş parçacığı, pipeline, NUMA, karmaşık caching gibi özelliklerle bazen bir cycle’dan kısa sürede işi bitirirken bazen de yüzlerce ya da binlerce cycle gerektiren işlemler üretiyor. Algoritmayı yalnızca innermost loop sayısıyla anlatmaya çalışmak gerçeği çarpıtabilir. Ayrıca Big-O konuşulacaksa Big-Omega gibi diğer gösterimlerden de mutlaka söz edilmeli. (Bu arada Big-O temalı animasyonu da keyifle izlemiştim)
- Big-O kuramı, tam da bu tür cihaza bağlı etkenlerden bağımsız olarak işlem miktarını tanımlamak için ortaya çıkmış bir kavram. Bu anlamda zamandan bağımsız bir araç. (İyi bir anlatıcı genelde “C gibi sabitler N küçükken çok önemli olabilir” demeyi de ihmal etmez)
Asıl ilginç olan, kuantum hesaplamada bazı işlemlerin atom sayısına göre O(n^7) büyümesi ama bilim insanlarının bu hesapları gerçekten çalıştırmaktan çekinmemesi. Çünkü N yeterince küçük, bilgisayarlar ve bellek sürekli hızlanıyor ve çıkan sonuçlar muazzam derecede değerli. (Bilgisayar bilimi uzmanı değilim; O() gösterimini yanlış kullandıysam kusura bakmayın)
- Sadece “n^7 ile orantılı büyür” demek yeterli. O(n^7) dersen çoğu kişi ne demek istediğini anlar ama matematikte O yalnızca bir “üst sınır” ifade ettiği için teknik olarak tam doğru değildir. Gerçekten kesin konuşmak istersen Ω(n^7) gibi yazmak daha doğru olur
Görselleştirme gerçekten çok hoşuma gitti. Algoritma derslerini yıllar önce almış olsam da görsel olarak görmek hâlâ çok yardımcı oluyor
Elektrik mühendisliği okuduğum için mi bilmiyorum ama Big O Notation bana hep bir şeylerin üstünkörü geçildiği bir kavram gibi geldi. Sanki herkes zaten biliyormuş gibi ele alındı ve gerçekten özenli bir açıklamaya pek rastlamadım. Bu kavramın hangi düzeyde matematik ya da bilgisayar bilimi dersinde ilk kez tanıtıldığını merak ediyorum
- Bilgisayar bilimi müfredatında Discrete Math dersinde Big-O’yu en sistemli şekilde öğrendim
- Benim okulumda Big-O ve çeşitli ispat yöntemleri Algorithm Analysis (zorunlu ders) kapsamında öğretiliyordu. Ama bu ders genelde 3. ya da 4. sınıfta alınıyordu ve öğrencilerin aslında daha 1. sınıftan itibaren bu kavramı bir ölçüde kapmış olduğu gibi örtük bir varsayım vardı (muhtemelen çevreden doğal olarak öğrenildiği düşünülüyordu)
- Matematiksel olarak f(x) fonksiyonunun O(g(x)) olması, f(x)/g(x) oranının bir C sabiti için “tüm x’ler için f(x)/g(x) < C” koşulunu sağlaması demektir. Bilgisayar biliminde f(x) çoğu zaman belli bir algoritmanın işlem sayısı gibi bir karmaşıklığı ifade eder
- Big-O Notation’ın tasarımı birden fazla yoruma açıktır. Örneğin bir algoritmayı Turing Machine üzerindeki adım sayısıyla tanımlarsan log zamanlı algoritma diye bir şey olamaz ve O(log n), O(1) sayılır
- Bilgisayar bilimi birinci sınıf zorunlu dersinde öğrendim. Çok da özel bir şey değil; girdi verisi arttıkça işlem miktarının nasıl arttığını anlatan bir kavram sadece. Dışarıdan zor görünse de aslında oldukça basit ve nettir
Dinamik görselleştirme anlamayı inanılmaz derecede kolaylaştırdı. Bunun gibi daha fazla ders/materyal hazırlanmasını isterim
- Bu geri bildirim beni gerçekten mutlu etti, teşekkürler
Big-O Notation hakkında bir başlık her açıldığında, birinin bu kavramın anime The Big O ile nasıl bağlantılı olduğunu açıklamasını umuyorum. Hâlâ o animenin tam olarak ne anlattığını bilmiyorum
- (4 kutu bira arka arkaya hüpletir)Tamam, dinle. O anime sırayla Pacific Rim, Dark City ve The Matrix’in birbirine karıştırılmış hâli gibi
Bana göre Big O Notation’ı en etkili şekilde anlamanın yolu, onu günlük hayattaki benzetmelerle ilişkilendirmek
Bence çok güzel bir materyal. Bir sinyal gönderdim, umarım yerine ulaşmıştır; sanki boş yere değil de küçük bir dopamin dozu almış gibi hissettim
- Ulaştı. Teşekkürler