Küçük o ve Küçük omega

Büyük O bir üst sınır verir ama sınırın sıkı olup olmadığını söylemez. $n$ fonksiyonu hem $O(n)$ hem $O(n^2)$’dir; ikinci ifade doğrudur ama bilgi vermez.

Bazı durumlarda söylemek istediğimiz şey daha güçlüdür: “$f$, $g$’den kesinlikle daha yavaş büyür.” Bu ders o ifadeyi mümkün kılan iki gösterimi tanımlar.

Küçük o

$$f(n) = o(g(n)) \iff \forall c > 0,\ \exists n_0 : \forall n \geq n_0,\ f(n) < c \cdot g(n)$$

Büyük O ile farkı niceleyicidedir. Büyük O’da “bir $c$ bulunur” denir; küçük o’da “her $c$ için” denir — sabit ne kadar küçük seçilirse seçilsin, yeterince büyük $n$ için eşitsizlik sağlanır.

Sonuç, $f$’nin $g$ yanında giderek önemsizleşmesidir. Eşdeğer ve kullanışlı biçimi limitle verilir:

$$f(n) = o(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = 0$$

Örneğin $n = o(n^2)$’dir, çünkü oran $1/n \to 0$’dır. Buna karşılık $3n$ ifadesi $o(n)$ değildir: oran sabit $3$’te kalır, sıfıra gitmez. Büyük O ise ikisini de kabul eder — $3n = O(n)$ doğrudur.

Küçük omega

$$f(n) = \omega(g(n)) \iff \lim_{n \to \infty} \frac{f(n)}{g(n)} = \infty$$

Küçük omega, küçük o’nun aynadaki görüntüsüdür: $f$, $g$’yi kesinlikle geride bırakır. $n^2 = \omega(n)$ ve $2^n = \omega(n^{100})$ doğrudur — üstel büyüme, her polinomu sonunda geçer.

Beş Gösterimin Benzeşimi

Beş gösterim, sayı karşılaştırmalarıyla birebir eşleşir:

Gösterim	Karşılaştırma benzeşimi	Limit ölçütü
$f = O(g)$	$f \leq g$	Oran sonlu (sıfır olabilir)
$f = \Omega(g)$	$f \geq g$	Oran sıfırdan büyük (sonsuz olabilir)
$f = \Theta(g)$	$f = g$	Oran sonlu ve sıfırdan büyük bir sabite gider
$f = o(g)$	$f < g$	Oran sıfıra gider
$f = \omega(g)$	$f > g$	Oran sonsuza gider

Benzeşim öğreticidir ama tam değildir; farkları bu dersin son bölümünde ele alınır.

Limit Ölçütü Uygulaması

Limit, iki fonksiyonun ilişkisini belirlemenin en pratik yoludur. Oran hesaplanır ve sonsuza giderken davranışına bakılır.

import math

def oran(f, g, n_degerleri):
    return [f(n) / g(n) for n in n_degerleri]

n_degerleri = [10, 100, 1_000, 10_000, 100_000]

print([f"{x:.4f}" for x in oran(lambda n: n, lambda n: n**2, n_degerleri)])
# ['0.1000', '0.0100', '0.0010', '0.0001', '0.0000']   — sıfıra gidiyor: n = o(n²)

print([f"{x:.4f}" for x in oran(lambda n: 3*n, lambda n: n, n_degerleri)])
# ['3.0000', '3.0000', '3.0000', '3.0000', '3.0000']   — sabit: 3n = Θ(n), o(n) değil

print([f"{x:.4f}" for x in oran(math.log2, lambda n: n, n_degerleri)])
# ['0.3322', '0.0664', '0.0100', '0.0013', '0.0002']   — sıfıra gidiyor: log n = o(n)

print([f"{x:.2f}" for x in oran(lambda n: n * math.log2(n), lambda n: n**2, n_degerleri)])
# ['0.33', '0.07', '0.01', '0.00', '0.00']             — n log n = o(n²)

Sayısal gözlem bir kanıt değildir; limitin gerçekten sıfıra gittiği matematiksel olarak gösterilir. Ancak beklentiyi doğrulamanın ve hata yakalamanın hızlı yoludur.

Üçüncü satır, sık kullanılan bir sonucu doğrular: logaritma, her pozitif kuvvetten yavaş büyür. Dördüncü satır ise $n \log n$ ile $n^2$ arasındaki farkın neden bu kadar belirleyici olduğunu gösterir — oran sıfıra gider, yani fark girdi büyüdükçe açılır.

Büyüme Hiyerarşisi

Küçük o, sık kullanılan fonksiyonları kesin bir zincire dizer. Her adımda soldaki, sağdakinin küçük o’sudur:

$$1 = o(\log \log n) = o(\log n) = o(n^{\varepsilon}) = o(n) = o(n \log n) = o(n^2) = o(2^n) = o(n!)$$

Burada $\varepsilon$, sıfırdan büyük herhangi bir sabittir. Zincir üç genel kuralı özetler:

• Logaritma, her pozitif kuvvetten yavaş büyür. $\log n = o(n^{0{,}001})$ bile doğrudur; logaritmanın kaç kez uygulandığı da fark etmez.
• Her polinom, her üstelden yavaş büyür. $n^{1000} = o(1{,}001^n)$ doğrudur; taban bire ne kadar yakın olursa olsun.
• Üstel, faktöriyelden yavaş büyür. $n!$ çarpanlarının ortalaması $n$ ile birlikte büyür, $2^n$’in çarpanları ise sabit kalır.

Zincirdeki her ilişki küçük o ile yazıldığından, aradaki ayrımlar kesindir; bir sınıftan diğerine geçmek sabit bir iyileştirme değil, mertebe değişimidir.

Aynı zincir, $\Theta$ ile küçük gösterimler arasındaki bağı da verir: $f = \Theta(g)$ ise $f$ ne $o(g)$ ne de $\omega(g)$’dir. Üç durum birbirini dışlar ve —oranın limiti varsa— birlikte tüm olasılıkları kapsar.

Ne İşe Yarar

Küçük gösterimler üç yerde kullanılır.

Sınıf hiyerarşisini kurmak. “$\log n = o(n)$ ve $n = o(n^2)$” ifadeleri, karmaşıklık sınıflarının kesin olarak ayrıldığını söyler. Büyük O ile aynı iddia yapılamaz; $O$ gevşek olabileceği için ayrımı göstermez.

İhmal edilebilirliği belirtmek. Bir ifadenin küçük terimi $o(\cdot)$ ile yazılırsa, “bu terim asimptotik olarak önemsizdir” denmiş olur: $n^2 + o(n^2)$ ifadesi, ikinci terimin baskın terimin yanında kaybolduğunu belirtir.

Kesin ayrım iddiası. İki algoritmanın farklı sınıflarda olduğu, ancak küçük gösterimlerle söylenebilir. “Birincisi $O(n^2)$, ikincisi $O(n \log n)$” ifadesi tek başına ikincisinin daha iyi olduğunu kanıtlamaz — birincinin sınırı gevşek olabilir. Kesin ifade, ikinci algoritmanın maliyetinin birincininkinin $o(\cdot)$’ı olduğudur.

Tam Sıralama Değildir

Karşılaştırma benzeşimi bir yerde bozulur: sayılarda iki değerden biri mutlaka diğerinden küçük, büyük veya ona eşittir. Fonksiyonlarda böyle bir güvence yoktur.

İki fonksiyon karşılaştırılamaz olabilir: aralarındaki oran salınırsa, ne limit vardır ne de bir sınır ilişkisi kurulabilir. Örneğin $n$ ile, tek $n$’lerde $n^2$ çift $n$’lerde $1$ değerini alan bir fonksiyon arasında hiçbir asimptotik ilişki yoktur.

def salinan(n: int) -> int:
    return n**2 if n % 2 == 1 else 1

print([salinan(n) / n for n in range(1, 8)])
# [1.0, 0.5, 3.0, 0.25, 5.0, 0.16666666666666666, 7.0]   — oran salınıyor

Oran ne sıfıra ne sonsuza yakınsar; ikisi arasında gidip gelir. Böyle bir fonksiyon $O(n)$ de değildir, $\Omega(n)$ de.

Pratikte karşılaşılan algoritma maliyetleri düzenli fonksiyonlardır ve bu sorun çıkmaz; ancak gösterimin bir kısmi sıralama olduğunu bilmek, ifadeleri dikkatli kurmayı gerektirir.

Özet

• Küçük o, sınırın kesinlikle gevşek olduğunu belirtir: her sabit için eşitsizlik sağlanır, oran sıfıra gider.
• Küçük omega, aynı ilişkinin ters yönüdür; oran sonsuza gider.
• Beş gösterim sayı karşılaştırmalarına benzer: $O \approx \leq$, $\Omega \approx \geq$, $\Theta \approx =$, $o \approx <$, $\omega \approx >$.
• Limit ölçütü, iki fonksiyonun ilişkisini belirlemenin pratik yoludur.
• Küçük gösterimler sınıf hiyerarşisini kurmak, ihmal edilebilirliği belirtmek ve kesin ayrım iddiasında bulunmak için kullanılır.
• İlişki tam sıralama değildir; oranı salınan fonksiyonlar karşılaştırılamaz.

Sonraki Adım

Gösterimler tanımlandı; sıra bunların temsil ettiği büyüme sınıflarına geldi. Sonraki ders, sabit zamandan faktöriyele uzanan sınıfları sayısal olarak karşılaştıracak ve “algoritma ne kadar büyük girdiyle başa çıkabilir” sorusunu yanıtlayacak.