Karmaşıklık
Karmaşıklık ve Big-O
Kod mülakatları için pratik bir giriş: Big-O ne demek, yaygın sınırlar, döngüleri nasıl analiz edersin, alan karmaşıklığı nerede devreye girer.
Big-O neyi ölçer?
Zaman karmaşıklığı, girdi boyutu n büyüdükçe algoritmanın yaptığı işin nasıl ölçeklendiğini söyler. Mülakatlarda genelde en kötü durum (worst-case) Big-O’su istenir; bazen ortalama durum da konuşulur (ör. hash map).
Big-O sabit çarpanları ve düşük dereceli terimleri yok sayar: 3n² + 100n + 5 → O(n²). Amaç “bu yaklaşım büyüdükçe yaşar mı?” sorusuna hızlı cevap vermektir.
Yaygın sınırlar
| Big-O | Ad | Tipik örnek | Ne zaman |
|---|---|---|---|
| O(1) | Sabit | Dizi indeksi, hash map ortalama get/put | Girdi boyutundan bağımsız iş |
| O(log n) | Logaritmik | İkili arama, dengeli ağaçta arama | Her adımda arama uzayını yarıya indir |
| O(n) | Doğrusal | Tek geçiş, dizi tarama | Her öğeye bir kez bak |
| O(n log n) | Lineeritmik | İyi sıralamalar (merge/heap), birçok “sırala + tara” | Sıralama veya böl-yönet birleştirme |
| O(n²) | Karesel | İç içe iki döngü, naif çift kontrolü | Her çift / her i,j |
| O(2ⁿ) | Üstel | Alt küme tam sayım, naif özyineleme | Her eleman dahil/hariç |
| O(n!) | Faktöriyel | Tüm permütasyonlar | Sıra sayımı (n küçük olmalı) |
Döngüleri nasıl sayarsın?
- Tek döngü
0..n→ genelde O(n). - İç içe iki döngü her biri
n→ O(n²). - İç döngü her seferinde yarıya iniyorsa (ikili arama tarzı) → O(n log n) veya tek arama için O(log n).
- Döngü + içeride O(n) kopya/sıralama → çarp: örn. her adımda sort → kolayca O(n² log n).
- Erken çıkış en kötü durumu iyileştirmez; Big-O hâlâ en kötü yolu anlatır.
Alan (space) karmaşıklığı
Girdi dışında ne kadar ek bellek kullanıyorsun? Çıktı dizisi bazen sayılır bazen “gerekli çıktı” diye ayrı tutulur, mülakatta netleştir. Özyineleme yığını da alandır: derinlik d ise çoğu zaman O(d) ek alan.
Yapılara göre kaba tablo
| Yapı | Erişim | Arama | Ekleme | Not |
|---|---|---|---|---|
| Dizi / liste | O(1) | O(n) | O(n)* | *Sona ekleme amortize O(1) olabilir |
| Hash map / set | - | O(1) ort. | O(1) ort. | Kötü hash / çarpışmada O(n) |
| Sıralı dizi | O(1) | O(log n) | O(n) | İkili arama mümkün |
| Yığın / kuyruk | O(1) uç | O(n) | O(1) | Uç işlemleri |
| Min/max heap | O(1) min | O(n) | O(log n) | Top-K ve öncelik |
| Dengeli BST | - | O(log n) | O(log n) | Sıralı gezinme |
Mülakat ipuçları
- Çözümü anlatırken zaman + alan ikilisini söyle; trade-off varsa belirt (ör. O(n) zaman / O(n) map vs O(n²) / O(1)).
- “Amortize” ve “ortalama” kelimelerini bilerek kullan; hash ve dinamik dizi için doğrudur.
- Kalıp seçimi çoğu zaman karmaşıklığı belirler: kayan pencere O(n), naif alt dizi O(n²).
- Bu sitede her yaklaşımda karmaşıklık rozetleri vardır, şablonu ezberle, sonra Big-O’yu kendi cümlelerinle savu.
Sonraki adım
Temel kalıplara geç: yol haritası, kalıp listesi, veya kaynaklar (platformlar, kitaplar, referanslar).