Karmaşıklık Hesaplama Yöntemi

Sınıflar tanındı; sıra bir kod parçasına bakıp hangi sınıfa ait olduğunu belirlemeye geldi. Bu ders, hesabın kurallarını verir. Kurallar azdır ve birleştirilerek uygulanır.

Temel Kurallar

Ardışık bölümler toplanır. İki bölüm arka arkaya çalışıyorsa maliyetleri toplanır ve büyük olan baskın kalır: $O(n) + O(n^2) = O(n^2)$.

Döngü, gövde maliyeti çarpı tur sayısıdır. Gövdesi sabit olan ve $n$ kez dönen döngü $O(n)$’dir.

İç içe döngülerde maliyetler çarpılır. Her ikisi de $n$ kez dönen iki döngü $O(n^2)$’dir.

Koşullu yapılarda en kötü dal alınır. Güvence en kötü durum üzerinden verilir.

Sabit sayıda tekrar sabittir. Kaç kez döndüğü $n$’e bağlı olmayan döngü $O(1)$’dir.

def sayim_ornekleri(n: int) -> dict[str, int]:
    sayac = {"tekli": 0, "icice": 0, "ucgen": 0, "yarilanan": 0}

    for i in range(n):                       # O(n)
        sayac["tekli"] += 1

    for i in range(n):                       # O(n²)
        for j in range(n):
            sayac["icice"] += 1

    for i in range(n):                       # O(n²) — üçgensel ama yine karesel
        for j in range(i):
            sayac["ucgen"] += 1

    i = 1
    while i < n:                             # O(log n)
        sayac["yarilanan"] += 1
        i *= 2

    return sayac


print(sayim_ornekleri(8))
# {'tekli': 8, 'icice': 64, 'ucgen': 28, 'yarilanan': 3}
print(sayim_ornekleri(16))
# {'tekli': 16, 'icice': 256, 'ucgen': 120, 'yarilanan': 4}

Girdi ikiye katlandığında sayılar sınıfların beklediği gibi değişir: tekli iki katına, iç içe dört katına çıkar; yarılanan döngü ise yalnızca bir artar.

Üçgensel döngü dikkat ister. Toplam tur sayısı $n(n-1)/2$’dir; sabit çarpan elendiğinde $O(n^2)$ kalır. “Yarısı kadar dönüyor” gözlemi sınıfı değiştirmez — yalnızca sabiti değiştirir.

Döngü Sınırının Değişimi

Tur sayısı, döngü değişkeninin nasıl ilerlediğine bağlıdır:

İlerleme	Tur sayısı	Sınıf
i += 1	$n$	$O(n)$
i += k	$n/k$	$O(n)$
i *= 2	$\log_2 n$	$O(\log n)$
i = i * i	$\log \log n$	$O(\log \log n)$
i -= 1 (n’den)	$n$	$O(n)$

İkinci satır önemlidir: sabit adımla ilerlemek sınıfı değiştirmez. Çarpımsal ilerleme ise değiştirir; ikili aramanın logaritmik olmasının kaynağı budur.

Özyineleme Bağıntıları

Özyinelemeli bir algoritmanın maliyeti, kendi cinsinden yazılır. Bu ifadeye özyineleme bağıntısı denir.

Üç yaygın kalıp:

$$T(n) = T(n-1) + O(1) \implies T(n) = O(n)$$

Her adımda problem bir eleman küçülür ve sabit iş yapılır; toplam $n$ adım. Faktöriyel hesabı bu kalıptadır.

$$T(n) = T(n/2) + O(1) \implies T(n) = O(\log n)$$

Her adımda problem yarılanır ve sabit iş yapılır; yarılama sayısı $\log_2 n$’dir. İkili arama bu kalıptadır.

$$T(n) = 2\,T(n/2) + O(n) \implies T(n) = O(n \log n)$$

Problem iki yarıya bölünür, her düzeyde tüm elemanlar işlenir. Birleştirmeli sıralama bu kalıptadır ve bir sonraki konunun ana örneğidir.

Özyineleme Ağacı

Bağıntıyı çözmenin sezgisel yolu, çağrıları bir ağaç olarak çizip düzey düzey maliyet toplamaktır.

$T(n) = 2T(n/2) + n$ bağıntısında:

Düzey	Çağrı sayısı	Çağrı başına iş	Düzey toplamı
0	1	$n$	$n$
1	2	$n/2$	$n$
2	4	$n/4$	$n$
$k$	$2^k$	$n/2^k$	$n$

Her düzeyin toplamı $n$’dir ve düzey sayısı $\log_2 n$’dir; toplam $n \log n$ çıkar.

Aynı yöntem $T(n) = 2T(n/2) + O(1)$ için farklı sonuç verir: düzey toplamları $1, 2, 4, \dots, n$ biçiminde büyür ve toplam $O(n)$ olur. Yaprak sayısı baskın hâle gelir.

Ana Teorem

Böl ve yönet bağıntılarının çoğu tek bir kalıba uyar:

$$T(n) = a\,T(n/b) + f(n)$$

Burada $a$ alt problem sayısı, $b$ küçülme çarpanı, $f(n)$ bölme ve birleştirme maliyetidir. Sonuç, $f(n)$ ile $n^{\log_b a}$ karşılaştırılarak belirlenir:

• $f(n)$ küçükse: $T(n) = \Theta(n^{\log_b a})$ — yapraklar baskın.
• İkisi aynı mertebedeyse: $T(n) = \Theta(n^{\log_b a} \log n)$ — tüm düzeyler eşit.
• $f(n)$ büyükse: $T(n) = \Theta(f(n))$ — kök baskın.

Birleştirmeli sıralamada $a = 2$, $b = 2$, $f(n) = n$’dir; $n^{\log_2 2} = n$ olduğundan ikinci durum geçerlidir ve sonuç $\Theta(n \log n)$ çıkar.

Teoremin tam ifadesi ek koşullar içerir ve her bağıntı bu kalıba uymaz; uymayanlar için ağaç yöntemi veya doğrudan çözüm kullanılır.

Amortize Çözümleme

Bazı işlemlerin maliyeti tek tek bakıldığında yanıltıcıdır. Veri Yapıları kursundaki dinamik dizi buna örnekti: sona ekleme çoğunlukla sabit, ara sıra doğrusaldır.

Toplam maliyet yöntemi, $m$ işlemin toplam maliyetini hesaplar ve $m$’e böler. Dinamik dizide $n$ ekleme için toplam kopyalama $n$’den azdı; ekleme başına amortize maliyet sabittir.

def toplam_kopyalama(n: int) -> int:
    """n eklemede yapılan toplam kopyalama sayısı (kapasite ikiye katlanarak)."""
    kapasite, uzunluk, kopyalama = 1, 0, 0
    for _ in range(n):
        if uzunluk == kapasite:
            kopyalama += uzunluk           # tüm elemanlar yeni bloğa taşınır
            kapasite *= 2
        uzunluk += 1
    return kopyalama


for n in (16, 1000, 100_000):
    print(n, toplam_kopyalama(n), f"{toplam_kopyalama(n)/n:.2f}")
# 16 15 0.94
# 1000 1023 1.02
# 100000 131071 1.31

Ekleme başına ortalama kopyalama sayısı, girdi büyüdükçe küçük bir sabitin çevresinde kalır; doğrusal büyümez. Amortize sabit maliyet ifadesi tam olarak bunu söyler.

İki yöntem daha vardır. Muhasebe yöntemi, her ucuz işleme ileride yapılacak pahalı iş için bir pay yükler; potansiyel yöntemi, yapının “biriken enerjisini” bir fonksiyonla ifade eder. Üçü de aynı sonucu verir; seçim, ispatın hangisiyle daha kısa yazıldığına bağlıdır.

Uygulama Sırası

Bir kod parçasının maliyetini bulmak için izlenen sıra:

1. Girdi büyüklüğünü tanımla. $n$ neyi sayıyor?
2. En iç işlemi bul. Hangi işlem en sık tekrarlanıyor?
3. Tur sayılarını çarp. İç içe yapılarda dıştan içe doğru.
4. Ardışık bölümleri topla, büyük terimi al.
5. Özyineleme varsa bağıntıyı yaz ve çöz.
6. Amortize davranış varsa toplam maliyeti işlem sayısına böl.

Adımlar sırayla uygulandığında, sezgiye başvurmadan sonuç elde edilir.

Özet

• Ardışık bölümler toplanır, iç içe döngülerde maliyetler çarpılır, koşullarda en kötü dal alınır.
• Döngü değişkeninin çarpımsal ilerlemesi tur sayısını logaritmik yapar; sabit adımla ilerleme sınıfı değiştirmez.
• Özyinelemeli maliyet bir bağıntıyla yazılır; üç yaygın kalıp doğrusal, logaritmik ve doğrusal-logaritmik sonuç verir.
• Özyineleme ağacı, düzey düzey maliyet toplayarak bağıntıyı çözer.
• Ana teorem, böl ve yönet bağıntılarını üç durumda sınıflandırır.
• Amortize çözümleme, bir işlem dizisinin toplam maliyetini işlem sayısına böler.

Sonraki Adım

Buraya kadar yalnızca zaman ele alındı. Oysa algoritmalar bellek de kullanır ve ikisi sıklıkla birbirinin yerine geçer: daha çok bellek kullanarak daha hızlı, daha az bellek kullanarak daha yavaş çalışmak mümkündür. Sonraki ders bu ödünleşimi ve tipik kalıplarını ele alacak.