Temeller
Büyüme hızları ve Big-O eğrileri
O(1)…O(n!) tek grafikte; n büyüdükçe her sınırın nasıl ölçeklendiğini izle.
Soru: n ≤ 10⁴ için O(n²) kabul edilebilir mi?
Cevap n’nin üst sınırına bağlıdır. 10⁴ × 10⁴ = 10⁸ işlem çoğu judge’ı zaten 1 saniyede aşar. Ama n ≤ 10⁵ ise O(n²) = 10¹⁰ ve çözüm zaman sınırına takılır. Bu sayfa, bir sınırı “yeterince hızlı mı?” sorusunu görsel ve sayısal cevaplayacak hıza getirmeyi amaçlar.
Sayılarla
| n | log₂ n | n | n log n | n² | 2ⁿ |
|---|---|---|---|---|---|
| 10³ | 10 | 10³ | 10⁴ | 10⁶ | ~10³⁰⁰ |
| 10⁶ | 20 | 10⁶ | 2·10⁷ | 10¹² | patlar |
| 10⁹ | 30 | 10⁹ | 3·10¹⁰ | 10¹⁸ | patlar |
Tek satırda: log n devasa n’de bile küçük kalır, n log n10⁶’da hâlâ yaşanır, n² 10⁵’i geçince ölmez, 2ⁿ n > 30’da fiziksel olarak imkânsızdır.
Nereden gelir?
Her döngü yapısı bir büyüme sınıfına karşılık gelir:
- Tek döngü 1..n: her elemana bir kez dokunursun →
O(n). - İç içe iki döngü, her ikisi de n: toplam iterasyon
n · n = n²→O(n²). İç döngü ortalaması n/2 olsa bile sabit katsayıyı atarsın, yineO(n²). - Böl-yönet her adımda yarıya iner: n → n/2 → n/4 → … 1. Bu yarılama
log₂ nkez olur. Her seviye diziyi bir kez birleştirir (n iş) →n · log n→ O(n log n). - Alt küme tarası: her eleman dahil/hariç iki seçenek →
2 · 2 · … · 2 = 2ⁿ→ O(2ⁿ).
Tuzak: “merge sort iç içe döngü içeriyor, O(n²) olmalı”
Yanlış. Merge sort’taki iç döngü tek bir seviye içindir ve her seviye tüm diziyi bir kezdokunur (n iş). İç içe gibi görünen kısım aslında log n seviyenin her birinde n iş:n · log n, n · n değil. Aynı yanılgı: “iki ayrı döngü var, O(n²)”. Ardışık iki döngü toplanır (n + n = 2n → O(n)), çarpılmaz.
Sıradaki adım
- Karmaşıklık ve Big-O: döngü sayma pratik hâli.
- Logaritmalar: log n neden “neredeyse sabit”.
- binary-search kalıbı: O(log n)’in doğduğu yer.
Alıştırma
Grafiği duraklatıp n = 20’ye getir. O(n²) ve O(n log n)değerlerini tahmin et, sonra fareyi üstlerinde tut. Şimdi n = 40’a çıkar: fark kaç kat büyüdü?