Karmaşıklık Sınıflarını Okumak

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.

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.

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.