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 |
n = 1000’de ne kadar iş?
Aşağıdaki logaritmalar 2 tabanlıdır; yalnızca sabiti değiştirir. n = 1000 iken log2(n) yaklaşık 10. Naif özyinelemeli Fibonacci Θ(φⁿ), kabaca O(1.618ⁿ). Buna O(2ⁿ) demek gevşek bir üst sınırdır. En kötü durumu söyle; ortalama veya amortize diyorsan belirt.
| Big-O | n = 1000 | Not |
|---|---|---|
| O(1) | 1 | Dizi indeksi. Hash get/put ortalama; kötü durumda O(n). |
| O(log n) | ~10 | İkili arama, dengeli BST. |
| O(n) | 1.000 | Tek geçiş. |
| O(n log n) | ~10.000 | Mergesort, heapsort, Timsort. |
| O(n²) | 1.000.000 | İç içe iki geçiş. |
| O(n³) | 1.000.000.000 | Floyd–Warshall, üç iç içe geçiş. |
| O(2ⁿ) | 2^1000 | Alt küme dahil/hariç. Her alt kümeyi somutlamak Θ(n · 2ⁿ). |
| O(n!) | 1000! | Tüm permütasyonlar. |
Cebir
- Sabitleri düş:
O(2n)→O(n). - Düşük terimleri düş:
O(n² + n)→O(n²). - Farklı girdiler ayrı kalır:
asonrabdöngüsüO(a + b). - İç içe iş çarpar: dışarıda
O(n), içerideO(m)→O(n · m). - Ardışık iş toplanır:
O(n)sonraO(m)→O(n + m).
Erken çıkış en iyi durumu iyileştirebilir. En kötü durum Big-O hâlâ en kötü yoldur.
Ek alan kaynakları
Yardımcı alan girdiyi dışarıda tutar. Söylerken belirt. Çıktı depolaması bazen ayrı sayılır; mülakatçının hangisini istediğini sor. Yerinde demek O(1) ek alan demektir. Girdinin kendisi yine O(n) kaplar.
| Kaynak | Ek alan |
|---|---|
| Sabit sayıda skaler | O(1) |
| Uzunluğu n olan dizi veya dizgi | O(n) |
| Özyineleme | O(derinlik) yığın |
| Özyinelemeli ikili arama | O(log n) yığın. Döngü biçimi O(1). |
| Girdinin hash map’i | O(n) |
Amortize maliyetler
α(n) ters Ackermann fonksiyonudur. Mülakatta göreceğin her yapıda en fazla 4’tür. Zorlanmış çarpışma zincirli bir hash tablosu çağrı başına O(n) kalır. Amortize O(1) çalışan bir hash varsayar.
| İşlem | En kötü çağrı | Amortize | Koşul |
|---|---|---|---|
| Dinamik dizi ekleme | O(n) | O(1) | Geometrik yeniden boyutlandırma |
| Hash tablo insert | O(n) | O(1) | Düzgün hash + yeniden boyutlandırma |
| Union-find | O(n) | O(α(n)) | Rank/size birleşimi ve path compression |
| Splay ağacı | O(n) | O(log n) | Bir işlem dizisi üzerinden amortize |
Üst tabloda yazılmayan ayrımlar
Canlı tablo dizi, hash map, sıralı dizi, yığın/kuyruk, heap ve dengeli BST’yi listeler. Aşağıdakiler o satırların açılımı.
| Yapı | İşlem | Zaman | Not |
|---|---|---|---|
| Dizi | Ortaya ekle / sil | O(n) | Elemanlar kayar |
| Tekli bağlı liste | Başta ekle / sil | O(1) | |
| Tekli bağlı liste | Tuttuğun düğümden sonra ekle | O(1) | Düğümü bulmak ayrı O(n) |
| Tekli bağlı liste | Tuttuğun düğümü sil | O(n) | Önceki düğüm gerekir; kuyrukta değilsen halefin değerini kopyalayabilirsin |
| Çift bağlı liste | Tuttuğun düğümü sil | O(1) | |
| Heap | n öğeden kur | O(n) | Floyd bottom-up; n push değil |
Sıralama
Stabil, eşit anahtarların orijinal sırasını korur demektir.
| Algoritma | En iyi | Ortalama | En kötü | Ek alan | Stabil | Not |
|---|---|---|---|---|---|---|
| Timsort | O(n) | O(n log n) | O(n log n) | O(n) | Evet | Python’un çalıştırdığı |
| Insertion | O(n) | O(n²) | O(n²) | O(1) | Evet | Neredeyse sıralı girdide en iyi |
| Bubble | O(n) | O(n²) | O(n²) | O(1) | Evet | O(n) en iyi durum swapped-flag ister |
| Selection | O(n²) | O(n²) | O(n²) | O(1) | Hayır | |
| Mergesort | O(n log n) | O(n log n) | O(n log n) | O(n) | Evet | |
| Heapsort | O(n log n) | O(n log n) | O(n log n) | O(1) | Hayır | |
| Quicksort | O(n log n) | O(n log n) | O(n²) | O(log n) ort. | Hayır | En kötü özyineleme derinliği O(n), ekstra alan da O(n) |
| Counting | O(n + k) | O(n + k) | O(n + k) | O(k) | Evet | k anahtar aralığı; tamsayı anahtar |
| Radix (LSD) | O(d(n + b)) | O(d(n + b)) | O(d(n + b)) | O(n + b) | Evet | d basamak, b taban |
| Bucket | O(n + k) | O(n + k) | O(n²) | O(n) | Kova içi sıralama stabiyse | Ortalama düzgün yayılım varsayar |
Graflar
Süreler komşuluk listesi varsayar. Komşuluk matrisi DFS ve BFS’i O(V²) yapar. Fibonacci heap ile Dijkstra O(E + V log V) olur; mülakatlar ikili-heap sınırını bekler. Döngü içeren bir grafa topolojik sıralama geçerli bir sıra üretmez. Kahn, kalan indegree’li düğüm bırakarak bunu bildirir.
| Algoritma | Zaman | Ek alan | Gerekir | Kalıp |
|---|---|---|---|---|
| DFS | O(V + E) | O(V) | graph-dfs | |
| BFS | O(V + E) | O(V) | Ağırlıksız en kısa yol (hop) | grid-graph-bfs |
| Dijkstra | O((V + E) log V) | O(V) | Negatif olmayan ağırlık; ikili heap sınırı | shortest-path-weighted |
| Bellman–Ford | O(VE) | O(V) | Negatif ağırlık serbest; V−1 turdan sonra bir tur daha negatif döngü yakalar | shortest-path-weighted |
| Floyd–Warshall | O(V³) | O(V²) | Tüm çiftler. Negatif kenar serbest. dist[i][i] < 0 negatif döngü | — |
| Topolojik sıralama | O(V + E) | O(V) | Yönlü asiklik graf | topological-sort |
| Kruskal | O(E log E) | O(V) | Yönsüz. Kenarları sırala, sonra union-find | minimum-spanning-tree |
| Prim | O(E log V) | O(V) | Yönsüz ve bağlı. İkili heap. Yoğun graf + dizi O(V²) | minimum-spanning-tree |
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), veya dil kartları: Python, TypeScript, C#.
Big-O eğrilerini görsel görmek için matematik temelleri - büyüme hızları, logaritmalar ve toplamlar sayfalarına bak.