Big O Kopya Kagidi - Bilmeniz Gereken Her Karmasiklik

Neden Bu Kopya Kağıdına İhtiyacınız Var

Kod yazarken çözümünüzün yeterince iyi olup olmadığını anlamaya çalışırken, karmaşıklıkların hızlı bir zihinsel sıralamasına ihtiyacınız var. O(n log n) iyi mi? O(n²) kabul edilebilir mi? O(n!) ne ki?

Bu yazı, algoritmalar hakkında öğrenmeye başladığımda elimde olmasını istediğim referanstır. Yer imlerine ekleyin. Geri dönün. Zamanla sindirin.

Sıralama: En İyiden En Kötüye

İşte en hızlıdan en yavaşa. Bu sırayı ezberleyin — tüm algoritma analizinin temelidir:

O(1) → O(log n) → O(n) → O(n log n) → O(n²) → O(n³) → O(2ⁿ) → O(n!)

O(n log n)'e kadar her şey genellikle verimli kabul edilir. O(n²) küçük girdiler için kabul edilebilir (n < 1.000). O(n²)'den kötü olan her şey genellikle daha iyi bir algoritmaya ihtiyacınız olduğu anlamına gelir.

Görsel Karşılaştırma

Aşağıdaki interaktif çubuk grafik, bu karmaşıklıkların farklı girdi boyutlarında nasıl karşılaştırıldığını gösteriyor. Her birini adım adım inceleyin — n büyüdükçe çubukların nasıl değiştiğine dikkat edin:

Her Karmaşıklık Nasıl Hissettiriyor

Matematiğin ötesine geçen bir sezgi vereyim:

| Karmaşıklık | Takma Ad | Nasıl Hissettiriyor | Gerçek Örnek | |---|---|---|---| | O(1) | Sabit | Anlık. Işık düğmesini çevirmek gibi. | Dizi indeksi, hash araması | | O(log n) | Logaritmik | Sözlükte kelime aramak — ortaya git, yarıyı seç, tekrarla. | İkili arama | | O(n) | Doğrusal | Kitabı sayfa sayfa okumak. Her şeye bir kez dokunmak. | Max bulma, doğrusal arama | | O(n log n) | Doğrusal-log | Bir deste kartı verimli sıralamak. | Merge sort, quick sort | | O(n²) | Karesel | Odadaki herkesi diğer herkesle karşılaştırmak. | Bubble sort, iç içe döngüler | | O(n³) | Kübik | Üç iç içe döngü. Nadiren kabul edilir. | Naive matris çarpımı | | O(2ⁿ) | Üstel | Açma/kapama anahtarlarının her kombinasyonunu denemek. | Güç kümesi, kaba kuvvet | | O(n!) | Faktöriyel | Her olası düzenlemeyi denemek. Çılgın büyüme. | Permütasyonlar, gezgin satıcı |

Pratik Girdi Boyutu Kılavuzu

İşte çoğu eğitimin atladığı inanılmaz faydalı bir şey — yaklaşık 1 saniyede her karmaşıklık hangi girdi boyutlarını kaldırabilir (saniyede ~100 milyon işlem varsayarak):

| Karmaşıklık | Max n (~1 sn) | Gerçek Dünya Anlamı | |---|---|---| | O(1) | Herhangi | Sınır yok | | O(log n) | Herhangi | Pratik sınır yok | | O(n) | ~100.000.000 | 1 sn'de 100M eleman işle | | O(n log n) | ~5.000.000 | 1 sn'de 5M eleman sırala | | O(n²) | ~10.000 | Sadece küçük veri setleri | | O(n³) | ~500 | Çok küçük veri setleri | | O(2ⁿ) | ~25 | Sadece küçük girdiler | | O(n!) | ~12 | Neredeyse hiçbir şey |

Yaklaşımınızı seçerken bu tabloyu kullanın. Girdiniz 1 milyon eleman olabiliyorsa, O(n log n) veya daha iyi gerekir.

Yaygın İşlemler Hızlı Referans

Diziler / Listeler

| İşlem | Zaman | Notlar | |---|---|---| | İndeksle erişim | O(1) | Doğrudan bellek erişimi | | Arama (sırasız) | O(n) | Her elemanı kontrol etmeli | | Arama (sıralı) | O(log n) | İkili arama | | Sona ekleme | O(1)* | Dinamik diziler için amortize | | Başa ekleme | O(n) | Tüm elemanları kaydırmalı | | Sıralama | O(n log n) | En iyi karşılaştırma tabanlı |

Hash Map / Set

| İşlem | Zaman | Notlar | |---|---|---| | Ekleme | O(1)* | Ortalama amortize | | Arama | O(1)* | Ortalama amortize | | Silme | O(1)* | Ortalama amortize | | Tümünü gezme | O(n) | Her elemana dokunur |

Ağaçlar (Dengeli BST)

| İşlem | Zaman | Notlar | |---|---|---| | Arama | O(log n) | Arama alanını yarılar | | Ekleme | O(log n) | Konum bul + ekle | | Silme | O(log n) | Bul + yeniden yapılandır | | Tümünü gezme | O(n) | Her düğümü ziyaret et |

Sıralama Algoritmaları

| Algoritma | En İyi | Ortalama | En Kötü | Alan | |---|---|---|---|---| | Quick Sort | O(n log n) | O(n log n) | O(n²) | O(log n) | | Merge Sort | O(n log n) | O(n log n) | O(n log n) | O(n) | | Heap Sort | O(n log n) | O(n log n) | O(n log n) | O(1) | | Bubble Sort | O(n) | O(n²) | O(n²) | O(1) | | Insertion Sort | O(n) | O(n²) | O(n²) | O(1) |

Yardımcı Zihinsel Modeller

Okuduğunuz veya yazdığınız kodun karmaşıklığını anlamaya çalışırken bu kısayollar işe yarar:

O(1): "Ne kadar veri olursa olsun anında cevap verebilirim."
O(log n): "Her adımda problemimi yarıya indiririm."
O(n): "Her elemana tam bir kez bakarım."
O(n log n): "Her şeye bakarım ve her biri için yarılama işlemi yaparım."
O(n²): "Her şeyi diğer her şeyle karşılaştırırım."
O(2ⁿ): "Her eleman için 2 seçeneğim var ve tüm kombinasyonları denerim."

Şüphe duyduğunuzda döngüleri sayın: 0 döngü = O(1), 1 döngü = O(n), 2 iç içe döngü = O(n²).

Pratik Problemler

Tüm karmaşıklık sınıfları için sezgi oluşturmak adına harika problemler:

Two Sum — O(n) hash map vs O(n²) kaba kuvvet
Merge Intervals — O(n log n) sıralama + O(n) birleştirme
3Sum — O(n²) sıralama + iki işaretçi
Longest Substring Without Repeating Characters — O(n) kayan pencere
Kth Largest Element — O(n) quickselect vs O(n log n) sıralama
Word Search — O(n × m × 4^L) geri izleme — üstel!

Sonuç

Bu kopya kağıdı, algoritma analizi için ihtiyacınız olan temelleri kapsıyor. Tavsiyem:

1. Sıralamayı ezberleyin: O(1) < O(log n) < O(n) < O(n log n) < O(n²) < O(2ⁿ) < O(n!) 2. Girdi boyutu tablosunu kullanın — çözümünüzün yeterince hızlı olup olmadığını hızlıca değerlendirin 3. Yaygın işlemleri bilin — çoğu tahmin edilebilir kalıpları takip eder 4. Pratik, pratik, pratik — ne kadar çok problem çözerseniz, karmaşıklıkları o kadar hızlı tanırsınız

Big O bir araçtır, sınav değil. Daha iyi kod yazmak ve daha akıllı mühendislik kararları vermek için kullanın. Bunun için var.

İyi kodlamalar!