--- title: 'Karmaşıklık Sınıflarını Okumak' source: 'https://academia.sh/tr/kurslar/algoritmalar/karmasiklik-siniflari' course: Algoritmalar language: tr updated: '2026-08-17T18:07:32+00:00' license: 'CC BY-SA 4.0' --- # Karmaşıklık Sınıflarını Okumak Sabit, logaritmik, doğrusal, doğrusal-logaritmik, polinom, üstel ve faktöriyel büyüme; ölçek büyütme davranışı ve pratik sınırlar. Gösterimler tanımlandı; bu ders onların temsil ettiği büyüme sınıflarını somutlaştırır. Amaç, bir maliyet ifadesini gördüğünde ne anlama geldiğini **sayısal olarak** bilmektir: $O(n^2)$ bir algoritmanın milyon elemanla çalışıp çalışamayacağı, tahmin değil hesap işidir. ## Sınıflar En yavaştan en hızlı büyüyene doğru sık karşılaşılan sınıflar: | Sınıf | Ad | Tipik örnek | |---|---|---| | $O(1)$ | Sabit | Dizi elemanına erişim, karma tablosunda arama | | $O(\log n)$ | Logaritmik | İkili arama, dengeli ağaçta arama | | $O(n)$ | Doğrusal | Diziyi tarama, en büyüğü bulma | | $O(n \log n)$ | Doğrusal-logaritmik | Verimli sıralama algoritmaları | | $O(n^2)$ | Karesel | İç içe iki döngü, temel sıralamalar | | $O(n^3)$ | Kübik | Üç boyutlu iç içe döngü, kaba matris çarpımı | | $O(2^n)$ | Üstel | Tüm alt kümeleri denemek | | $O(n!)$ | Faktöriyel | Tüm sıralamaları denemek | Aradaki bazı sınıflar da vardır — $O(\sqrt{n})$, $O(n \log \log n)$, $O(n^{2{,}37})$ gibi — ancak yukarıdaki liste pratiğin büyük bölümünü kapsar. ## Sayısal Karşılaştırma Sınıflar arasındaki fark, birkaç sayı yazılınca görünür hâle gelir. ```python import math def islem_sayisi(n: int) -> dict[str, float]: return { "log n": math.log2(n), "n": n, "n log n": n * math.log2(n), "n²": n**2, "2ⁿ": 2**n if n <= 40 else float("inf"), } for n in (10, 100, 1_000, 1_000_000): d = islem_sayisi(n) print(n, {k: f"{v:.3g}" for k, v in d.items()}) # 10 {'log n': '3.32', 'n': '10', 'n log n': '33.2', 'n²': '100', '2ⁿ': '1.02e+03'} # 100 {'log n': '6.64', 'n': '100', 'n log n': '664', 'n²': '1e+04', '2ⁿ': 'inf'} # 1000 {'log n': '9.97', 'n': '1e+03', 'n log n': '9.97e+03', 'n²': '1e+06', '2ⁿ': 'inf'} # 1000000 {'log n': '19.9', 'n': '1e+06', 'n log n': '1.99e+07', 'n²': '1e+12', '2ⁿ': 'inf'} ``` Bir milyon elemanda logaritmik bir algoritma **yirmi** adım atar; karesel bir algoritma **bir trilyon**. Aradaki fark, "biraz daha yavaş" değil, bir problemi çözülebilir olmakla olmamak arasındaki farktır. Üstel sütunun kırkın üzerinde hesaplanmaması bir kolaylık değil, zorunluluktur: $2^{100}$ değeri, evrendeki atom sayısı mertebesindedir. ## Ölçek Büyütme Davranışı Pratikte en yararlı soru şudur: **girdi ikiye katlanırsa maliyet nasıl değişir?** | Sınıf | Girdi $2\times$ olduğunda maliyet | Girdi $10\times$ olduğunda | |---|---|---| | $O(1)$ | Değişmez | Değişmez | | $O(\log n)$ | Sabit bir miktar artar | Sabit bir miktar artar | | $O(n)$ | $2\times$ | $10\times$ | | $O(n \log n)$ | $2\times$'ten biraz fazla | $10\times$'ten biraz fazla | | $O(n^2)$ | $4\times$ | $100\times$ | | $O(n^3)$ | $8\times$ | $1000\times$ | | $O(2^n)$ | Karesi alınır | Anlamsız | Bu tablo, ölçüm yapmadan tahmin yürütmeyi sağlar. Bin kayıtla iki saniye süren karesel bir işlem, on bin kayıtla iki yüz saniye sürer. Aynı iş doğrusal-logaritmik bir algoritmayla yapılıyorsa, on kat veriyle yaklaşık on üç kat artış olur. Ters yönde de kullanılır: ölçülen sürelerin girdiyle nasıl değiştiğine bakarak algoritmanın sınıfı tahmin edilebilir. Girdi ikiye katlandığında süre dörde katlanıyorsa, kodda karesel bir davranış vardır. ## Alt Doğrusal Sınıflar $O(\log n)$ ve $O(\sqrt{n})$ gibi sınıflar, girdinin **tamamını okumadan** sonuç üretir. Bu ancak veri önceden düzenlenmişse mümkündür: ikili arama sıralılık varsayar, karma tablosu önceden kurulmuş bir tablo varsayar. Bu nedenle alt doğrusal maliyetler genellikle bir **önişleme** maliyetiyle birlikte gelir. Bir dizi sıralanıp sonra bin kez aranacaksa, $O(n \log n)$ sıralama maliyeti bin aramaya bölünür ve kendini fazlasıyla öder. Tek bir arama için sıralamak ise anlamsızdır. Karar ölçütü budur: **önişleme maliyeti, sorgu sayısına bölündüğünde kazanç kalıyor mu?** ## Neden $n \log n$ Sık Görünür Bu sınıf, iki nedenle sık karşımıza çıkar. Birincisi, **böl ve yönet** yapısının doğal sonucudur: problem her adımda ikiye bölünür ($\log n$ derinlik), her düzeyde tüm elemanlar işlenir ($n$ iş). Birleştirmeli sıralama bunun kanonik örneğidir. İkincisi, karşılaştırmaya dayalı sıralamanın **alt sınırıdır**: hiçbir karşılaştırmalı algoritma bundan hızlı olamaz. Bu sonuç, arama ve sıralama konusunda kanıtlanacaktır. ## Üstel Sınıflar ve Kombinatoryel Patlama Üstel ve faktöriyel sınıflar, "tüm olasılıkları dene" biçimindeki çözümlerden doğar: - $n$ elemanın tüm alt kümeleri: $2^n$ tane. - $n$ elemanın tüm sıralamaları: $n!$ tane. ```python import math for n in (10, 20, 30, 50): print(n, f"2^n = {2**n:.3g}", f"n! = {math.factorial(n):.3g}") # 10 2^n = 1.02e+03 n! = 3.63e+06 # 20 2^n = 1.05e+06 n! = 2.43e+18 # 30 2^n = 1.07e+09 n! = 2.65e+32 # 50 2^n = 1.13e+15 n! = 3.04e+64 ``` Otuz elemanla alt küme sayısı bir milyarı aşar; yirmi elemanla sıralama sayısı iki kentilyona ulaşır. Bu, kaba kuvvet çözümlerinin neden yalnızca çok küçük girdilerde kullanılabildiğini gösterir. Böyle problemlerde üç yol izlenir: girdiyi küçük tutmak, akıllı budama ile arama uzayını daraltmak (Programlama Temelleri kursundaki geri izleme), ya da kesin çözümden vazgeçip yaklaşık sonuç üretmek. Bu problemlerin kuramsal sınıflandırması **Hesaplama Kuramı** kursuna aittir. ## Sabitler Ne Zaman Önemli Asimptotik gösterim sabitleri eler, ancak gerçek dünyada sabitler vardır ve küçük girdilerde baskındır. $100n$ maliyetli bir algoritma ile $n^2$ maliyetli bir algoritma karşılaştırıldığında, ikincisi $n < 100$ için daha hızlıdır. Kesişim noktası, sabitlerin oranıyla belirlenir. Pratik sonucu, kütüphane gerçekleştirimlerinde görülür: sıralama algoritmaları küçük alt dizilerde eklemeli sıralamaya geçer, çünkü o boyutlarda basit algoritmanın küçük sabiti kazanır. Bu tür karma yaklaşımlar, asimptotik çözümlemenin nerede bitip ölçümün nerede başladığını gösterir. ## Özet - Sınıflar, sabit ve logaritmikten üstel ve faktöriyele doğru sıralanır; aradaki farklar büyük girdilerde mertebe düzeyindedir. - Girdi ikiye katlandığında maliyetin nasıl değiştiği, sınıfı tanımanın pratik yoludur. - Alt doğrusal sınıflar önceden düzenlenmiş veri gerektirir; önişleme maliyeti sorgu sayısına bölünerek değerlendirilir. - $n \log n$, böl ve yönet yapısının doğal sonucu ve karşılaştırmalı sıralamanın alt sınırıdır. - Üstel ve faktöriyel sınıflar kaba kuvvet çözümlerinden doğar ve yalnızca çok küçük girdilerde uygulanabilir. - Sabitler küçük girdilerde baskındır; kütüphaneler bu nedenle karma yaklaşımlar kullanır. ## Sonraki Adım Sınıflar tanındı; sıra bir kod parçasına bakıp hangi sınıfa ait olduğunu **belirlemeye** geldi. Sonraki ders, döngülerin, özyinelemenin ve amortize edilmiş işlemlerin maliyetini hesaplama yöntemlerini adım adım kuracak.