Maliyetin Büyümesi

Big O, girdi büyüdükçe maliyetin nasıl büyüdüğünü ölçer. Sabit faktörü değil — oranı. N=100’de ikisi de “birkaç milisaniye” içinde çalışan iki algoritma, biri O(N) ve diğeri O(N²) ise N=10.000’de 10.000 kat fark yaratabilir.

Yaygın Karmaşıklık Sınıfları

O(1) — Sabit. N’den bağımsız olarak aynı maliyet. Örnekler: anahtarla hash tablosu arama, diziye indeksle erişim, yığın push/pop. N’yi iki katına çıkarmak hiçbir şeyi değiştirmez.

O(log N) — Logaritmik. Her adım kalan işi ikiye böler. Örnekler: sıralı dizide ikili arama, oyun motorunda BVH uzamsal sorgu, dengeli ikili ağaç işlemleri. N=1.000.000 için: log₂(1.000.000) ≈ 20 adım.

O(N) — Doğrusal. Maliyet girdiye göre artar. Örnekler: bir listenin doğrusal taranması, bir dosyanın okunması, bir koleksiyondaki öğelerin sayılması. N=10.000 için: 10.000 işlem.

O(N log N) — Doğrusal-logaritmik. Neredeyse doğrusal, biraz daha kötü. Örnekler: birleştirme sıralaması, verimli en kısa yol algoritmaları (yığın ile Dijkstra). N=10.000 için: ~133.000 işlem.

O(N²) — Karesel. Maliyet patlar. Örnekler: aynı liste üzerinde döngü içinde list.contains() çağrısı, kabarcık sıralaması, naif tüm-çift karşılaştırma. N=1.000 için: 1.000.000 işlem. N=10.000 için: 100.000.000 işlem.

O(2^N) — Üstel. Herhangi anlamlı bir ölçekte kullanılamaz. Örnekler: kaba kuvvet kombinatoryal arama, tüm alt kümeleri bulma. N=30’da: 1.000.000.000’dan fazla işlem.

Görünür Hale Gelen Ölçek

N=10 karşılaştırması:
O(N):   10
O(N²):  100
oran:  10x

N=1.000 karşılaştırma:
O(N):   1.000
O(N²):  1.000.000
oran:  1.000x

N=10.000 karşılaştırma:
O(N):   10,000
O(N²):  100,000,000
oran:  10,000x

N=10 olduğunda fark neredeyse fark edilmez. N=10,000 olduğunda O(N²) algoritması 10,000 kat daha yavaş çalışır. Bu yüzden MOAD-0001 onlarca yıl boyunca görünmez kaldı: 1993’te üzerinde çalıştığı grafikler 50 düğüme sahipti. 2020’ye gelindiğinde aynı kod 50,000 düğümlü bağımlılık grafikleri üzerinde çalışıyordu.

Üç İşlemi Sınıflandır

Karmaşıklık sınıflarını somut işlemlere uygula. Her biri için anahtar soru: N büyüdükçe kaç işlem gerekir?

Doğru Kod, Yanlış Büyüme Eğrisi

O(N²) sürede çalışan doğru kod, O(N) kodla aynı sonuçları üretir. Testler geçer. Çıktı eşleşir. Hiçbir hata oluşmaz. Kusur, büyüme eğrisinde gizlidir.

Bu özellik, O(N²) kusurları tortul hale getirir: çalışan kodun içinde katılaşırlar ve yalnızca N belirli bir eşiği aştığında görünür hale gelirler. Kod değişmedi. Değişen, kodun etrafındaki dünyaydı.

MOAD-0001: Tortul Kusur

En yaygın örnek: grafik dolaşma döngüsü içinde visited = [] kullanımı.

visited = []
for node in graph:
if node not in visited:  # her çağrıda O(N) tarama
visited.append(node)
process(node)

Her not in visited çağrısı 0 ile len(visited)-1 arasındaki öğeleri tarar. N çağrı × ortalama N/2 taranan öğe = toplam O(N²). Çözüm: tek satır.

visited = set()  # O(1) üyelik testi
for node in graph:
if node not in visited:  # O(1) hash araması
visited.add(node)
process(node)

Aynı davranış. Aynı çıktı. Aynı testler geçiyor. Büyüme hızı O(N²) seviyesinden O(N) seviyesine düşüyor. N=1.000'de: 1.000× daha hızlı. N=10.000'de: 10.000× daha hızlı.

Hamming'in Dönemi Neden Bunu Tetikledi

Erken Java ve C'de ArrayList (dinamik dizi) varsayılan sıralı kapsayıcıydı. Set'ler vardı ama yaygın kullanımda değildi — geliştiriciler bildikleri yapılara yöneliyordu. 1993'te N=50 için visited = [] ile yapılan bir grafik dolaşımı mikrosaniyeler içinde çalışıyordu. Bu kod sürüm kontrolüne girdi, kopyalandı, kütüphanelere sarıldı ve paket yöneticileriyle dağıtıldı. 2020'ye gelindiğinde aynı desen, 50.000 düğümlü bağımlılık grafikleri üzerinde çalışıyordu.

Kod 1993'te doğruydu. Çevresindeki dünya değişince pahalı hale geldi. Hamming'in dönemi, büyüme hızı sorusunu hiç sormayarak bu tür kusurların temelini attı.

Tanı Koy ve Düzelt

Tanıyı uygula: O(N²) desenini bul, düzeltmeyi belirle.

Hangi İsimlendirme Değişiklikleri

Big O’nun bir adı olmadan önce programcılar “bu yavaş çalışıyor” diye fark ediyorlardı. Profil çıkarıyor, yeniden yazıyorlardı. Ancak bu kalıbı öğretemiyorlardı — yalnızca örnekleri gösterebiliyorlardı. Adı olmayan bir kalıp yayılamaz.

Big O’nun bir adı olduktan sonra, kıdemli bir mühendis “bu O(N²), yerine bir set kullan” diyebiliyor ve genç bir mühendis bu kalıbı anlayıp uygulayabiliyor ve başkalarına öğretebiliyordu. İsim, kalıbı aktarılabilir bir bilgi birimine dönüştürdü.

Hamming bu dinamiği başka alanlarda da fark etmişti. 1960’larda “spaghetti code” ifadesinin isimlendirilmesinin, herkesin deneyimlediği ancak kimsenin adını koyamadığı bir hata sınıfını tanıma, tartışma ve sonunda ortadan kaldırma imkânı sağladığını anlatmıştı. Aynı mekanizma karmaşıklık sınıfları için de geçerlidir.

Unhamming, Hamming’in atladığı kelime dağarcığını ekler: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Bu isimler, okuduğunuz kodda büyüme eğrisini görmenizi, ölçekte performansı tahmin etmenizi ve düzeltmeleri kesin biçimde iletmenizi sağlar. Hamming’in temel kavram testiyle uyumludurlar: kalıcı ve alanın geri kalanının çoğunu üretken kılarlar. [TITLE who_coined_big_o/]

Sayılar Teorisinden Bilgisayar Bilimine

Big O gösterimi bilgisayar biliminde ortaya çıkmadı. Saf matematikte — özellikle sayılar teorisinde — Donald Knuth’un algoritmalar için uyarlamasından 74 yıl önce doğdu.

Paul Bachmann, 1894

Alman matematikçi Paul Bachmann, 1894 tarihli Die Analytische Zahlentheorie (Analitik Sayılar Teorisi) adlı kitabında O gösterimini tanıttı. Bir niceliğin, sabit bir çarpana kadar başka bir nicelikten daha hızlı büyümeyeceğini ifade etmek için kompakt bir yol gerekiyordu. “f(n) = O(g(n))” yazmak şunu söylüyordu: f, en fazla g kadar hızlı büyür. Bu, sayılar teorisyenlerinin yaklaşımlardaki hata terimlerini tam sabitleri takip etmeden tartışmasına olanak sağladı.

Bachmann, döngüler, veri yapıları ya da çalışma süresi hakkında düşünmüyordu. Asal sayıların dağılımı — özellikle Asal Sayılar Teoremi’ndeki hata terimleri — hakkında düşünüyordu.

Edmund Landau, 1909

Başka bir Alman matematikçi olan Edmund Landau, 1909 tarihli Handbuch der Lehre von der Verteilung der Primzahlen (Asal Sayıların Dağılımı Üzerine El Kitabı) adlı eserinde gösterimi popülerleştirdi. Landau ayrıca ilgili küçük-o (o) gösterimini de tanıttı ve asimptotik sembol ailesini o kadar yoğun kullandı ki bu aile Bachmann-Landau gösterimi ya da kısaca Landau gösterimi olarak anılmaya başlandı.

Altmış yıl boyunca O gösterimi tamamen matematik alanında kaldı. Hiçbir programcı bunu düşünmüyordu.

Donald Knuth, 1968 & 1976

Donald Knuth, gösterimi bilgisayar bilimine taşıdı. The Art of Computer Programming (Cilt 1, 1968) adlı eserinde algoritmaların çalışma süresini tanımlamak için O gösterimini kullandı — Bachmann’ın aracını yeni bir alana doğrudan aktarmıştı. Algoritma analizine bu gösterimi sistematik olarak uygulayan ilk kişi oydu.

1976’da Knuth, SIGACT News dergisinde “Big Omicron and Big Omega and Big Theta” başlıklı kısa bir makale yayımladı. Alt sınırlar için Omega (Ω) ve sıkı sınırlar için Theta (Θ) gösterimlerini tanıttı; böylece bilgisayar biliminin bugün kullandığı üç sembollü söz dağarcığını tamamladı. Ayrıca bu sembollerin kullanımının alanda standartlaştırılması için çağrıda bulundu — bu bilinçli standardizasyon çabası, gösterimin hızla benimsenmesini hızlandırdı.

1980’lerin başına gelindiğinde Big O her algoritma ders kitabında yer alıyordu. 1990’lara gelindiğinde ise standart mülakat terminolojisi haline gelmişti.

74 Yıllık Bir Yolculuk

1894 — Bachmann, sayı teorisinde O gösterimini tanıttı
1909 — Landau, O, o ve tüm gösterim ailesini popülerleştirdi
1953 — Hamming, Bell Labs'ta araştırmalarına başlar (Big O'yu hiçbir zaman CS aracı olarak öğrenmez)
1968 — Knuth, TAOCP Cilt 1'de algoritma analizinde O gösterimini uygular
1976 — Knuth, Omega ve Theta'yı ekler; standardizasyon için tartışır
1980'ler — Big O, tüm CS müfredatlarına girer
1993 — MOAD-0001 üretim kodunda tortu katmanı oluşturur
1995 — Hamming, dersinin son versiyonunu öğretir; Big O'yu hiçbir zaman kapsamaz
2026 — MOAD-0001, 1.000'den fazla açık kaynak projede bulunur

Bachmann'ın aracı 74 yıl boyunca saf matematikte kaldı; her matematikçiye görünürken her programcıya görünmezdi. Knuth bu aracı yeni alana taşıdı. Hamming — aynı dönemde aynı hesaplama topluluğuyla çalışırken — bunu derslerine hiçbir zaman dahil etmedi.

Knuth'un Standardizasyonunun Neden Önemli Olduğu

Knuth'un 1976 tarihli makalesi Omega ve Theta'yı tanıtmaktan öte bir şey yaptı. Alanın tutarlı bir gösterime ihtiyacı olduğunu ve tutarsız gösterimin aktif olarak zararlı olduğunu savundu. Farklı ders kitapları O'yu farklı anlamlarda kullanıyordu — bazen üst sınır, bazen yaklaşık değer, bazen de sabitlerin önemli olup olmadığını belirtmeden. Knuth bu karmaşayı temizledi.

Bu, Hamming'in örüntü-adlandırma dinamiğinin doğrudan gösterime uygulanmasıdır. Knuth sembolleri standartlaştırmadan önce mühendisler karmaşıklık iddialarını ders kitapları, makaleler veya ekipler arasında kesin biçimde iletemiyordu. Standardizasyondan sonra "bu O(N log N) sürede çalışır" ifadesi, kim söylüyorsa söylesin, tam olarak tek bir anlama geldi.

Knuth ayrıca gayriresmi çeviriyi de sundu: "O(f(n)), çalışma süresinin, yeterince büyük tüm n değerleri için f(n)'in en fazla sabit katı olduğu anlamına gelir." Bu yorum — üst sınır, sabit çarpanla, büyük girdiler için — her programcının öğrendiği standart sezgiye dönüştü.