Temeller
Logaritmalar ve üsler
Böl-yönet’te log n neden çıkar; O(2ⁿ) arkasındaki üs kuralları.
Soru: 10⁹ elemanlı dizide binary search kaç adımda biter?
Cevap ≈ 30. Sebebi logaritma. Bu sayfa, log n’in neden devasa girdilerde bile neredeyse sabit gibi davrandığını ve mülakatta nerelerde çıkacağını açar.
Sayılarla: yarılama derinliği
Binary search her adımda arama uzayını ikiye böler. n’den 1’e inmek için kaç yarılama gerekir?
n = 16: 16 → 8 → 4 → 2 → 1 = 4 adım = log₂ 16.n = 10⁶: ≈ 20 adım.n = 10⁹: ≈ 30 adım.
n’i 10 katına çıkarınca adım sayısı yalnızca ~3.3 artar (log₁₀ 10 = 1, ama log₂ 10 ≈ 3.3). Bu yüzden log n “neredeyse sabit” hissettirir: n patlarken adım sayısı yavaşça yükselir.
Nereden gelir?
Her yarılama bir seviye: bir tamponun yarıya bölünmesi (merge sort), bir arama uzayının ikiye inmesi (binary search), bir ağacın bir derinlik inmesi (dengeli BST). Seviye sayısı, n’i 1’e indirinceye kadar kaç kez 2’ye böldüğündür, yani log₂ n.
Her seviyede n iş varsa (merge sort birleştirme), toplam: (seviye sayısı) × (seviye başına iş) = log₂ n × n = n log n. Tek bir arama için (binary search) tek bir yolda inersin, o yüzdenlog n.
Tuzak: “taban önemli, log₂ ve log₁₀ farklı”
Big-O’da değildir. logₐ n = log_b n / log_b a, yani tabanlar birbirinin sabit katıdır. Sabitleri Big-O atar: log₂ n, log₁₀ n, ln n hepsiO(log n). Sadece gerçek adım sayısı söylendiğinde taban önemli (binary search ikiye böler → taban 2).
Sıradaki adım
- Karmaşıklık ve Big-O: log n’in sınıfla yeri.
- Büyüme hızları: log’un diğer sınıflarla karşılaştırması.
- Toplamlar: merge sort’un n log n’i nereden alır.
Alıştırma
Aşağıdaki grafiği n = 1000’e getir. O(log n) ve O(√n)değerlerini tahmin et. Şimdi n = 10000’e çıkar: log kaç kat büyüdü, √n kaç kat? Bu, log’un “sabit gibi” hissiyatını somutlaştırır.