--- title: 'Küçük o ve Küçük omega' source: 'https://academia.sh/tr/kurslar/algoritmalar/kucuk-o-ve-kucuk-omega' course: Algoritmalar language: tr updated: '2026-08-17T18:07:34+00:00' license: 'CC BY-SA 4.0' --- # Küçük o ve Küçük omega Sıkı olmayan sınırların tanımı, limit ölçütü, beş gösterimin karşılaştırma işleçleriyle benzeşimi ve sıralama ilişkisinin sınırları. 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. ```python 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. ```python 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.