Karmaşıklık Nasıl Artar

Big O, girişin büyüdükçe maliyetin nasıl büyüdüğünü ölçer. Sabit faktör değil, büyüme oranı. N=100'te her ikisi de 'birkaç milisaniye' sürünen iki algoritma, N=10,000'te biri O(N) zamanla, diğeri O(N²) zamanla 10,000 kat farklı bir faktörle ayrılabilir.

Sıklıkla Karşılaşılan Karmaşıklık Sınıfları

O(1) — Sabit. N'e bağlı olarak maliyet aynı kalır. Örnekler: anahtarla hash tabanı arama, dizel erişim, diz üstü push/pop. N'i iki kat artırdığında hiçbir şey değişmez.

O(log N) — Logaritmik. Her adım kalan işi yarıya indirir. Örnekler: sıralı bir dizide ikili arama, oyun motorunda BVH alan sorgusu, dengeli ikili ağaç operasyonları. N=1,000,000 olduğunda: log₂(1,000,000) ≈ 20 adım.

O(N) — Lineer. Maliyet girişle büyür. Örnekler: bir listeyi lineer tarayarak, bir dosyayı okurken, bir koleksiyonun içindeki öğelerin sayısını sayma. N=10,000 olduğunda: 10,000 işlemi gerçekleştirir.

O(N log N) — Lineeritmix. Çok yakın bir şekilde lineer, biraz daha kötü. Örnekler: birleştirme sıralaması, (Dijkstra ile bir küme kullanarak) etkili en kısa yol algoritmaları. N=10,000 olduğunda: ~133,000 işlemi gerçekleştirir.

O(N²) — Karesel. Maliyet patlar. Örnekler: aynı listeyi dolaşarak list.contains() çağrısı, kabarcık sıralaması, basit tüm çiftler karşılaştırması. N=1,000 olduğunda: 1,000,000 işlemi gerçekleştirir. N=10,000 olduğunda: 100,000,000 işlemi gerçekleştirir.

O(2^N) — Eksponansiyel. Anlamlı herhangi bir ölçekte kullanılamıyor. Örnekler: brute-force kombinatorik, tüm alt kümeleri bulma. N=30 olduğunda: 1 milyar işlem.

Görselleştirme Ölçüsü

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

N=1,000 karşılaştırmalar:
  O(N):   1,000
  O(N²):  1,000,000
  oran:  1,000x

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

N=10 olduğunda, fark hemen görülmez. N=10,000 olduğunda, O(N²) algoritma 10,000 kat daha yavaş çalışır. Bu nedenle, MOAD-0001 1993'te çalıştığı grafolarda 50 düğüm vardı. 2020'de aynı kod, 50.000 düğümle çalışan bağımlılık grafıklarında çalışıyordu.

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

Karmaşıklık sınıflarını somut işlemlere uygulayın. Her birinin ana sorusu: N büyüdükçe kaç işlem gerektiği?

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

O(N²) zamanla çalışan doğru kod, O(N) kodla aynı sonuçları üretir. Testler geçer. Çıktı uyuşur. Hiçbir istisna atılmaz. Eksikliktin büyüme eğrisinde saklı.

Bu özelliğe N² (N karesine) yaramazlık sedimenter denir: Çalışan kodun içinde kalsifik olurlar ve N, bir eşiğin üstünde büyüdüğünde sadece görünür olurlar. Kod değiştirilmedi. Çevresi değişti.

MOAD-0001: Yaramaz Sedimentary

En yaygın örnek: visited = [] bir grafı tarayıcı döngü içinde.

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

not in visited her çağrıda 0'a kadar visited-1 öğesini tarar. N çağrı × N/2 ortalama taranan öğe = O(N²) toplam. Fix: bir satır.

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

Aynı davranış. Aynı çıktı. Aynı testler geçer. Büyüme hızı O(N) den O(N²) den değişir. N=1.000'de: 1.000 kat hızlı. N=10.000'de: 10.000 kat hızlı.

Hamming'in Yaşam Dönemi Bu Nedenle Etkiledi

Erken Java ve C'de, ArrayList (dynamik dizi) varsayılan sekans containerdı. Setler vardı ama idiomatik değildi - geliştiriciler ne kadar tanıdıkları şeylere ulaştılar. 1993'te bir grafı tarayıcı döngü N=50'de mikrosaniyeler içinde çalıştı visited = []. Bu kod sürüm kontrolüne girdi, kopyalandı, kütüphanelere sarıldı, paket yöneticilerinde gönderildi. 2020'de, aynı desen 50.000 düğümle dependency grafı üzerinde çalışıyordu.

1993'te kod doğruydu. Çevresi değiştiğinde pahalı hale geldi. Hamming'in Yaşam Dönemi, bu sınıftaki yaramazlığı atayan büyüme hızı sorusunu asla adlandırmadı.

Tanı ve Tedavi

Tedaviyi uygulayın: O(N²) deseni bulun, düzeltme tanımlayın.

Adlandırma Değişiklikleri

Big O'ya bir isim yoktu, programcılar 'hızlı çalışıyor' dedi ve profilleştirdi. Yeniden yazdılar. Ama bu deseni öğretmek yerine sadece örnekleri gösterdiler. Bir desen ismsizse, yayılamaz.

Big O'ya bir isim olduktan sonra, bir kıdemli mühendis 'bu O(N²), bir setle değiştirin' diyebilirdi ve bir genç mühendis bu deseni anlar, uygular ve öğretirdi. İsim, deseni bilgi birimi hâline getiriyordu.

Hamming, diğer alanlarda bu dinamikayı anladı. 1960'larda 'spaghetti code' adını koymasıyla topluluk, bu tür bir kusuru tanımlayabilip tartışabilip ve sonunda herkes bu kusuru yaşadı ama ismi yoktu. Bu mekanizma karmaşıklık sınıfları için de geçer.

Unhamming, Hamming'in atladığı sözcükleri ekliyor: O(1), O(log N), O(N), O(N log N), O(N²), O(2^N). Bu isimler, okuduklarınızda büyüme eğrisini görmene, ölçeklenebilir performansları tahmin etmenize ve tam olarak iletişim kurmanızı sağlar. Hamming'in bile temel için kendi testini karşılayan bir test için temel sağlarlar.

Sayı Kuramı'ndan Bilgisayar Bilimi'ne

Big O sembolizmi bilgisayar bilimiyle başlamadı. 74 yıl önce Donald Knuth tarafından algoritmalar için adapte edilmeden önce saf matematik - özellikle sayı teorisi - içinde ortaya çıktı.

Paul Bachmann, 1894

Paul Bachmann, bir Alman matematikçi, 1894'te Die Analytische Zahlentheorie (Analitik Sayı Kuramı) adlı kitabında O sembolünü tanıttı. Bir miktarı başka bir miktarın büyümesinin üzerinde büyümediğini ifade etmek için kompakt bir yol arıyordu. 'f(n) = O(g(n))' yazarak: f, g'nin büyümesinin üzerinde büyüyor deme şansını sağladı. Bu, yaklaşık değerlerde hata terimlerini düşünmek için sayı teorisyenlerine izin verdi ve tam olarak sabitleri takip etmek zorunda kalmadılar.

Bachmann, döngüler, veri yapıları veya yürütme hızı hakkında düşünmüyordu. Aslen, asal sayıların dağıtımını düşünüyordu - özellikle asal sayı teoreminde hata terimleri.

Edmund Landau, 1909

Edmund Landau, başka bir Alman matematikçi, 1909'da Handbuch der Lehre von der Verteilung der Primzahlen (Asal Sayıların Dağılımı Üzerine El Kitabı) adlı eserinde sembolü popülerleştirdi. Ayrıca, ilgili notasyonlar o (küçük-o) ve Landau asimetri sembol ailesini yaygın olarak kullandığı için Bachmann-Landau sembolizmi veya basitçe Landau sembolizmi olarak bilinen Landau asimetri sembol ailesini tanıttı.

Altı onyırdır, O sembolü sadece matematikte kullanıldı. Bir programcı, O sembolünden bahsetmedi.

Donald Knuth, 1968 & 1976

Donald Knuth, sembolü bilgisayar bilimi alanına aktardı. Bilgisayar Bilimi Sanatı (Cilt 1, 1968) adlı eserinde, Knuth, algoritmaların çalışma süresini tanımlamak için O sembolünü kullandı - bu, Bachmann'ın aracı bir başka alana doğrudan nakliydi. O notationun sistemli olarak analize uygulayan ilk kişi oldu.

1976'da, Knuth, 'Büyük Omicron ve Büyük Omega ve Büyük Theta' adlı kısa bir makaleyi SIGACT News adlı yayınında yayınladı. Aşağı sınırlar için Omega (Omega) ve sıkı sınırlar için Theta'ı tanıttı ve bugün bilgisayar bilimi kullandığı üç sembol sözcüğünü tamamladı. Ayrıca, bu sembollerin kullanımının alanın tümünde standartlaştırılması gerektiği için argument etti - bu, kabulün hızlanmasına katkıda bulunan bir amaçlı standartlaştırma eylemi.

1980'lerin başlarında, Big O her algoritmalar ders kitabında yer aldı. 1990'larda, standart sözlük olarak kabul edildi.

74 Yılın Bir Seyahat

1894 - Bachmann, O sembolünü sayı teorisi için tanıttı
1909 - Landau, O, o ve tüm sembol ailesini popülerleştirdi
1953 - Hamming, Bell Labs'ta araştırma yapmaya başladı (hiç CS aracı olarak Big O öğrenmedi)
1968 - Knuth, TAOCP Cilt 1'de algoritmaların analizine O uyguladı
1976 - Knuth, Omega ve Theta ekledi; standartlaştırma için argument etti
1980'ler - Big O, tüm CS ders kitaplarında yer aldı
1993 - MOAD-0001 tortu tabakası üretim kodu içinde oluşmaya başladı
1995 - Hamming, son versiyonunu öğretti; Big O'yi asla kapsamadı
2026 - MOAD-0001, 1000'den fazla açık kaynak proje içinde bulunmuş oldu

Bachmann'ın aracı, 74 yıl boyunca saf matematikte kullanıldı ve her matematikçi tarafından görüldü, ancak her programcı tarafından görülmedi. Knuth, nakliyi gördü. Hamming - aynı dönemde, aynı bilgisayar topluluğuyla işbirliği içinde - kursuna Big O'yi dahil etmedi.

Knuth'un Standartlaştırmanın Önemi Nedeniyle

Knuth'un 1976'daki makalesi, sadece Omega ve Theta'ı tanıttı. Bilginin tutarlı bir nota sahip olması gerektiğini ve tutarlı olmayan nota'nın aktif olarak zararlı olduğunu savundu. Farklı ders kitapları, O sembolünü farklı şeyleri temsil etmek için kullandı - bazen üst sınır, bazen yaklaşık, bazen de sabitlerin önemli olup olmadığı konusunda belirtilmedi. Knuth, bu durumu düzeltti.

Bu, Hamming'in sembol adlandırma dinamiği ile notasyonun kendisinin uygulamasıdır. Knuth'un sembolleri standartlaştırdığı zamanlar, mühendisler, kitaplar, makaleler veya takımlar arasında karmaşıklık iddialarını kesin olarak iletişim kuramıyorlardı. Standartlaşmadan sonra, 'bu O(N log N) çalışır' ifade ettiği tek anlamı, kim söylediği önemli değil.

Knuth ayrıca, sözlü çeviri olarak da katkıda bulundu: 'O(f(n)) , büyük enough n için, çalıştırma süresinin en fazla f(n) sabit faktörle katlanması demektir.' Bu yorum - büyük girişler için üst sınır, sabit faktörle katlanmak - her programcı tarafından öğretilen standart anlayış oldu.