Kod Yapısı Karmaşıklığı Nasıl Ortaya Çıkarır

Koddan Big O'yu Nasıl Tanımlayacaksınız

Big O kodunuzun şeklinde gizlidir. Dört desen çoğu durumu kapsar:

N öğe üzerinde tek döngü: O(N)

# O(N): one pass through the list
for item in list_of_n_items:
    process(item)

İç içe döngüler, her biri N öğe üzerinde: O(N²)

# O(N²): every item paired with every other item
for item_a in list_of_n_items:
    for item_b in list_of_n_items:
        compare(item_a, item_b)

Sabit zamanlı arama: O(1)

Dizi indeksi erişimi, hash tablosu araması — boyut ne olursa olsun bir adım.

Böl ve Yönet (her adımda sorunu yarıya bölün): O(log N)

İkili arama: her kontrol kalan öğeleri yarıya böler.

---

Gizli O(N²): bir döngünün içindeki bir liste

# This looks like O(N) but it is actually O(N²)
visited = []
for item in list_of_n_items:
    if item not in visited:   # scans all of visited: O(N)
        visited.append(item)  # the whole loop: O(N²)

if item not in visited satırı, visited'in her öğesini her yinelemede tarar. Bir liste taraması O(N) maliyeti vardır. N kez çalışan bir döngü, her biri O(N) iş yapıyor: O(N) × O(N) = O(N²).

Bu desen 1.000+ açık kaynaklı projede görülür. Düzeltme bir karakter alır: visited = [] yerine visited = set() yazın. Set üyeliği testi O(1) maliyeti vardır, O(N) değil. Bir değişiklik. Aynı sonuçlar. N=1.000'de 1.000× daha hızlı.

Bu Kodu Sınıflandırın & Düzeltin

Bu kodu okuyun:

result = []
for name in student_names:
    if name not in result:
        result.append(name)

Teori Uygulamaya Buluşuyor

Doğada Big O

Big O sadece teori değildir. Saniyeler içinde biten programları 17 dakika alan programlardan ayırır — tam aynı görevde.

Gerçek örnek: bir derleme sisteminde bağımlılık döngüsü algılanması.

Yazılım yüklerken, bilgisayarınız bir bağımlılık grafiğini çözer: paket A, B'ye ihtiyaç duyar, B, C'ye ihtiyaç duyar ve bu şekilde devam eder. Bir derleme sistemi bu grafiği döngüler için kontrol eder.

Bir O(N²) döngü algılama algoritması N=100 pakette iyi çalışır. N=50.000 pakette (gerçek bir proje): 17 dakika alır. O(N) düzeltmesi: 10 saniye.

Bu tam hata GHC (Haskell derleyicisi), pip (Python paket yöneticisi), Maven (Java derleme sistemi), Cargo (Rust paket yöneticisi) ve 1.000+ diğer projede mevcuttur.

Yazarları dikkatsiz olduğu için değil. visited = [] N küçükken yazıldı. Kod katılaştı. N büyüdü. Yapı yarım saat alana kadar kimse fark etmedi.

Big O, ne olduğunu adlandırmanızı ve düzeltmenizi sağlayan kelime dağarcığıdır.

---

Daha derinlemesine gitmek ister misiniz? unhamming kursumuz Big O hakkında tam bir bölüm, MOAD-0001 (1.000+ açık kaynak projede bulunan gerçek bir O(N²) hatasıdır) ve bir deseni adlandırmanın neden bunu her yerde bulmanıza izin verdiğini içerir. Bkz. Eksik Bölüm: Algoritmik Karmaşıklık.

Derleme Sürelerini Tahmin Edin

Bir derleme sistemi O(N²) döngü algılaması kullanır.

Ölçülen derleme süreleri:

- N=100 paket: 0.01 saniye

- N=1.000 paket: 1 saniye

O(N²) için: zaman (N_yeni / N_eski)² olarak ölçeklenir.

O(N) için: zaman (N_yeni / N_eski) olarak ölçeklenir.