Böl ve Yönet

Önceki derste kaba kuvvet tek parça olarak koştu ve bütün olasılıkları gördü. İlk tasarım kalıbı bu bütünlüğü bozar: problemi aynı türden daha küçük iki kopyaya indirir, her birini özyinelemeyle çözer ve iki çözümü birleştirir. Bu kalıbın adı böl ve yönet (divide and conquer).

Algoritmalar kursu bu kalıbın üç örneğini çoktan ölçtü: birleştirmeli sıralama, hızlı sıralama ve ikili arama. Bu ders o yordamları tekrarlamaz. Ölçtüğü şey bağıntının kendisidir ve sorduğu soru şudur: bölme ile birleştirme ayrı hesaplardır; birleştirme adımı eksik kaldığında kaç girdide yanlış yanıt çıkar, ve bölmenin adım kazandırmadığı girdi büyüklüğü nerede biter.

• TY11. Ölçülen problem: bir dizide toplamı en büyük bitişik alt dizi. Alt dizi boş olamaz, yani yanıt en kötü durumda tek bir elemandır.
• TY12. Kâhin bütün bitişik alt dizileri görür; 12 elemanlı bir dizide 78 alt dizi vardır.
• TY13. Bir adım, bir elemanın toplama eklenip karşılaştırılmasıdır. Özyineleme çağrısının kendisi de bir adımdır ve ayrıca sayılır.
• TY14. Bölme kuralı bütün değişkelerde aynıdır: dizi ortadan ikiye ayrılır, yani bağıntıda $a = 2$ ve $b = 2$.
• TY15. Birleştirme üç değişkede ölçülür — doğrusal, karesel, eksik. Üçü de aynı bölmeyi kullanır; aralarındaki tek fark birleştirmedir.
• TY16. Kalıbın ön koşulu: birleştirme adımı, çözümün sınırı geçen biçimini de kapsamalıdır. Eksik birleştirme yalnız bu ön koşulu bozar.
• TY17. Uzunluk süpürmesi 2’den 128’e ikişer kat; her uzunlukta yine 40 dizi.
• TY18. M01/K04’ün sıralama ve arama yordamları tekrarlanmaz; buradaki ölçü bağıntının kendisidir.
• TY19. Her ölçüm 20260219 tohumlu ikinci dağarcıkta da koşturulur.

Bölmenin Bağıntısı

Bir böl ve yönet yordamı üç işten oluşur: problemi $a$ parçaya bölmek, her parçayı özyinelemeyle çözmek, ve parçaların çözümlerini birleştirmek. Parçalar özgün problemin $1/b$ boyunda ise maliyet şu bağıntıyı sağlar:

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

Burada $f(n)$ birleştirmenin maliyetidir ve bölmenin kendisini de içerir. Ana teorem, bu bağıntının çözümünü $f(n)$ ile $n^{\log_b a}$ arasındaki yarışa bakarak verir. Üç durum vardır: birleştirme özyinelemeden ucuzsa maliyeti özyineleme belirler ve sonuç $\Theta(n^{\log_b a})$ olur; ikisi aynı büyüklükteyse araya bir $\log n$ çarpanı girer ve sonuç $\Theta(n^{\log_b a} \log n)$ olur; birleştirme baskınsa sonuç doğrudan $\Theta(f(n))$’dir.

Bu dersin bölmesinde $a = 2$, $b = 2$ ve $\log_b a = 1$. Yani yarış, birleştirmenin doğrusal olup olmadığı üzerinedir. Doğrusal birleştirme ikinci duruma düşer ve $\Theta(n \log n)$ verir; karesel birleştirme üçüncü duruma düşer ve $\Theta(n^2)$ verir — yani kaba kuvvetle aynı büyüklüğe. Bölme değişmediği hâlde sonuç değişir; bu, bölme ile birleştirmenin ayrı hesaplar olduğunun biçimsel ifadesidir. Ana teoremin bir sınırı da burada anılmalıdır: parçalar eşit boyda değilse ya da $f(n)$ üç durumun hiçbirine düşmüyorsa teorem yanıt vermez, bağıntı doğrudan açılarak çözülür. Bu dersin bölmesi eşit olduğu için o durumla karşılaşılmaz.

Kâhin ve Problem

Ölçülen problem, sınırı geçen çözümün var olduğu en yalın problemdir: en büyük toplamlı bitişik alt dizi. Kâhin bütün alt dizileri sayar.

# Ortak cerceve: dagarcik ve adim sayaci (onceki dersten aynen).
TOHUM = 20260218


def uretec(tohum):
    d = tohum

    def sonraki(n):
        nonlocal d
        d = (d * 1103515245 + 12345) % 2147483648
        return d % n
    return sonraki


def dagarcik(tohum=TOHUM, n=40, uzunluk=12):
    r = uretec(tohum)
    return [{"no": i + 1, "dizi": [r(30) - 9 for _ in range(uzunluk)]}
            for i in range(n)]


class Sayac:
    def __init__(self):
        self.adim = 0

    def say(self, n=1):
        self.adim += n


def kahin_en_buyuk(dizi, s):
    """Butun bitisik alt dizileri gorur. Hakem budur."""
    en_iyi = dizi[0]
    for i in range(len(dizi)):
        toplam = 0
        for j in range(i, len(dizi)):
            s.say()
            toplam += dizi[j]
            if toplam > en_iyi:
                en_iyi = toplam
    return en_iyi


K = dagarcik()
s = Sayac()
yanit = [kahin_en_buyuk(k["dizi"], s) for k in K]
print("dagarcik:", len(K), "dizi x 12 deger | kahin toplam adim:", s.adim)
print("dizi basina adim:", s.adim // len(K), "= 12 x 13 / 2")
print("ilk uc yanit:", yanit[:3])

dagarcik: 40 dizi x 12 deger | kahin toplam adim: 3120
dizi basina adim: 78 = 12 x 13 / 2
ilk uc yanit: [52, 55, 84]

Kâhin dizi başına 78 adım, kırk dizide 3120 adım harcıyor ve girdiye göre değişmiyor. Yanıtların büyüklüğü de anlamlıdır: ilk üç dizide 52, 55 ve 84. Dağarcığın değerleri en çok 20 olduğuna göre bu yanıtlar birden çok elemanı kapsıyor demektir; yani çözüm neredeyse hiçbir zaman tek bir elemanda değil.

Üç Birleştirme, Tek Bölme

Aşağıdaki yordam üç değişkeyi tek gövdede taşır. Bölme her üçünde aynıdır; değişen tek şey sınırı geçen çözümün nasıl hesaplandığıdır.

# Onceki blogun uzerine: dagarcik, Sayac, kahin_en_buyuk ve K oradan gelir.
def bol_yonet(dizi, s, birlestirme="dogrusal"):
    """T(n) = 2 T(n/2) + birlestirme(n). Birlestirme SINIRI GECEN cozumu bulur."""
    def coz(bas, son):
        s.say()                                   # ozyineleme cagrisi da bir adimdir
        if son - bas == 1:
            return dizi[bas]
        orta = (bas + son) // 2
        sol = coz(bas, orta)
        sag = coz(orta, son)
        if birlestirme == "eksik":                # SINIRI GECEN COZUM ATLANIYOR
            return max(sol, sag)
        if birlestirme == "karesel":              # dogru ama pahali birlestirme
            sol_uc, t = [], 0
            for i in range(orta - 1, bas - 1, -1):
                s.say()
                t += dizi[i]
                sol_uc.append(t)
            sag_uc, t = [], 0
            for j in range(orta, son):
                s.say()
                t += dizi[j]
                sag_uc.append(t)
            en = None
            for a in sol_uc:                      # her sinir cifti ayri deneniyor
                for b in sag_uc:
                    s.say()
                    if en is None or a + b > en:
                        en = a + b
            return max(sol, sag, en)
        en_sol, t = None, 0                       # dogrusal birlestirme
        for i in range(orta - 1, bas - 1, -1):
            s.say()
            t += dizi[i]
            if en_sol is None or t > en_sol:
                en_sol = t
        en_sag, t = None, 0
        for j in range(orta, son):
            s.say()
            t += dizi[j]
            if en_sag is None or t > en_sag:
                en_sag = t
        return max(sol, sag, en_sol + en_sag)
    return coz(0, len(dizi))


def olc(birlestirme, kume):
    ayrilan, ak, ah = [], 0, 0
    for k in kume:
        s1, s2 = Sayac(), Sayac()
        if bol_yonet(k["dizi"], s1, birlestirme) != kahin_en_buyuk(k["dizi"], s2):
            ayrilan.append(k["no"])
        ak += s1.adim
        ah += s2.adim
    return {"ayrilan": len(ayrilan), "ayrilan_no": ayrilan[:6],
            "kalip_adim": ak, "kahin_adim": ah, "oran": round(ah / ak, 2)}


for ad in ("dogrusal", "karesel", "eksik"):
    print(f"{ad:9s} birlestirme:", olc(ad, K))

dogrusal  birlestirme: {'ayrilan': 0, 'ayrilan_no': [], 'kalip_adim': 2680, 'kahin_adim': 3120, 'oran': 1.16}
karesel   birlestirme: {'ayrilan': 0, 'ayrilan_no': [], 'kalip_adim': 5320, 'kahin_adim': 3120, 'oran': 0.59}
eksik     birlestirme: {'ayrilan': 40, 'ayrilan_no': [1, 2, 3, 4, 5, 6], 'kalip_adim': 920, 'kahin_adim': 3120, 'oran': 3.39}

Üç sayı yan yana. Kâhin 3120 adım. Doğrusal birleştirme 2680 adım harcıyor — kâhinin 1,16 katı azı — ve 40 girdinin hiçbirinde ayrılmıyor. Karesel birleştirme 5320 adım harcıyor, yani kâhinden 1,71 kat yavaş, ve o da 40 girdide ayrılmıyor. Eksik birleştirme 920 adım harcıyor, kâhinin 3,39 katı azı, ve 40 girdinin 40’ında ayrılıyor.

İki okuma birlikte durur. Birincisi: doğru olmak hızlı olmayı gerektirmez. Karesel birleştirme yanıtı hep doğru veriyor ama kaba kuvvetten yavaş; bölme burada hiçbir şey kazandırmıyor, üstelik özyineleme çağrılarının kendi adımını da ekliyor. İkincisi: hızlı olmak doğru olmayı gerektirmez. Eksik birleştirme en ucuz olanı ve tam olarak bu yüzden kullanılası görünüyor; oysa yanıtı 40 girdide de yanlış.

Eksik değişkenin ne döndürdüğüne bakmak yanılgının yapısını gösterir. Sınırı geçen çözüm atlandığında özyineleme yaprağa kadar iner ve her düzeyde iki yarının en iyisi alınır; geriye kalan tek aday, dizinin en büyük tek elemanıdır. Kâhinin ilk üç yanıtı 52, 55 ve 84 iken eksik birleştirmenin yanıtı en çok 20 olabilir. Yanılgı bir hesap hatası değil, çözüm uzayının bir bölgesinin hiç ziyaret edilmemesidir — önceki dersin örnekleme yanılgısıyla aynı biçim, bu kez özyineleme sınırında.

Bağıntı Sayıya Dönüşürken

Ana teoremin iki durumu, uzunluk büyütüldüğünde ölçülen adımda görünür hâle gelir.

# Onceki bloklarin uzerine: dagarcik, Sayac, kahin_en_buyuk, bol_yonet oradan gelir.
print("uzunluk  kahin adim  dogrusal adim   oran  karesel adim   oran")
for uzunluk in (2, 4, 8, 16, 32, 64, 128):
    kume = dagarcik(uzunluk=uzunluk)
    s1, s2, s3 = Sayac(), Sayac(), Sayac()
    for k in kume:
        kahin_en_buyuk(k["dizi"], s1)
        bol_yonet(k["dizi"], s2, "dogrusal")
        bol_yonet(k["dizi"], s3, "karesel")
    print(f"{uzunluk:7d} {s1.adim:11d} {s2.adim:14d} {s1.adim / s2.adim:6.2f}"
          f" {s3.adim:14d} {s1.adim / s3.adim:6.2f}")

uzunluk  kahin adim  dogrusal adim   oran  karesel adim   oran
      2         120            200   0.60            240   0.50
      4         400            600   0.67            840   0.48
      8        1440           1560   0.92           2680   0.54
     16        5440           3800   1.43           8600   0.63
     32       21120           8920   2.37          28760   0.73
     64       83200          20440   4.07         101080   0.82
    128      330240          46040   7.17         371160   0.89

Doğrusal birleştirmenin oranı 0,60’tan 7,17’ye çıkıyor ve 1’i 8 ile 16 arasında geçiyor. Bunun anlamı açıktır: bölme, 8 elemana kadar hiçbir şey kazandırmıyor, tersine kaybettiriyor. Uzunluk 2’de böl ve yönet kâhinin neredeyse iki katı adım harcıyor; kazanç ancak 16’da başlıyor. Kayıp özyineleme çağrılarından gelir — $n$ elemanlı bir dizide $2n - 1$ çağrı yapılır ve bunların hiçbiri kaba kuvvette yoktur. Bu, gerçek gerçeklenimlerin küçük parçalarda özyinelemeyi kesip doğrudan çözüme geçmesinin ölçülmüş nedenidir.

Karesel birleştirmenin oranı ise 0,50 ile 0,89 arasında kalıyor ve hiçbir uzunlukta 1’i geçmiyor. Oran yavaşça 1’e yaklaşıyor, çünkü iki yordam da $\Theta(n^2)$ büyüyor ve aradaki fark sabit bir çarpandır. Ana teoremin üçüncü durumu tam olarak budur: birleştirme baskın olduğunda bölmenin verdiği $\log n$ kazancı ortadan kalkar ve geriye yalnız özyinelemenin ek yükü kalır. Bölmek bir kazanç değildir; birleştirme ucuzsa kazançtır.

Toplam adımı iki bileşene ayırmak, ana teoremin ikinci durumunu doğrudan görünür kılar.

# Onceki bloklarin uzerine: dagarcik, Sayac ve bol_yonet oradan gelir.
from math import log2
print("uzunluk  cagri  birlestirme  dizi basina toplam   n x log2(n)")
for uzunluk in (8, 16, 32, 64, 128):
    kume = dagarcik(uzunluk=uzunluk)
    s = Sayac()
    for k in kume:
        bol_yonet(k["dizi"], s, "dogrusal")
    cagri = 2 * uzunluk - 1
    toplam = s.adim // len(kume)
    print(f"{uzunluk:7d} {cagri:6d} {toplam - cagri:12d} {toplam:20d}"
          f" {int(uzunluk * log2(uzunluk)):13d}")

uzunluk  cagri  birlestirme  dizi basina toplam   n x log2(n)
      8     15           24                   39            24
     16     31           64                   95            64
     32     63          160                  223           160
     64    127          384                  511           384
    128    255          896                 1151           896

Birleştirme sütunu ile son sütun birebir aynı: 24, 64, 160, 384, 896. Bağıntının çözümü burada bir yaklaşıklık değil, sayılan bir eşitliktir — her düzeyde toplam $n$ adım harcanır ve $\log_2 n$ düzey vardır. Çağrı sütunu ise $2n - 1$ olarak ayrı büyür ve doğrusaldır; küçük $n$’de baskın, büyük $n$’de önemsiz olan bileşen budur. Uzunluk 8’de çağrılar toplamın %38’ini yer, 128’de %22’sini. Bölmenin küçük girdide kaybetmesinin sayısal kaynağı tam olarak bu orandır.

İkinci Dağarcık

# Onceki bloklarin uzerine: dagarcik, Sayac ve bol_yonet oradan gelir.
IKINCI = 20260219
for ad, tohum in (("birinci dagarcik (20260218)", TOHUM),
                  ("ikinci  dagarcik (20260219)", IKINCI)):
    kume = dagarcik(tohum)
    print(ad)
    for birlestirme in ("dogrusal", "eksik"):
        o = olc(birlestirme, kume)
        print(f"  {birlestirme:9s} ayrilan {o['ayrilan']:2d} / 40 | oran",
              round(o["ayrilan"] / 40, 4), "| kalip adim", o["kalip_adim"])

birinci dagarcik (20260218)
  dogrusal  ayrilan  0 / 40 | oran 0.0 | kalip adim 2680
  eksik     ayrilan 40 / 40 | oran 1.0 | kalip adim 920
ikinci  dagarcik (20260219)
  dogrusal  ayrilan  0 / 40 | oran 0.0 | kalip adim 2680
  eksik     ayrilan 39 / 40 | oran 0.975 | kalip adim 920

Doğrusal birleştirmenin adımı iki dağarcıkta birebir aynı: 2680. Bu şaşırtıcı değildir, çünkü bu yordamın adım sayısı yalnız uzunluğa bağlıdır, değerlere değil — kaba kuvvette de, böl ve yönette de erken çıkış yoktur. Eksik birleştirmenin ayrılan girdisi 40’tan 39’a iniyor; oran 1,0000’den 0,9750’ye. Fark bir girdidir ve çözünürlüğün altındadır, yani ölçülmemiş sayılır. İkinci dağarcıkta ayrılmayan tek dizi dokuzuncudur: on iki değerinin onu sıfır ya da negatiftir ve tek büyük değeri olan 20, hem en büyük elemandır hem de en büyük alt dizi toplamıdır. Eksik birleştirme orada doğru yanıtı yanlış nedenle verir — sınırı geçen çözümü yine hiç aramamış, yalnız aradığı şey bu kez yeterli olmuştur. Bir kalıbın tek bir girdide kâhinle uyuşması, ön koşulunun sağlandığı anlamına gelmez; ölçünün 40 girdi üzerinden alınmasının nedeni budur.

Özet

• Böl ve yönet bağıntısı $T(n) = a \cdot T(n/b) + f(n)$’dir; bu derste $a = 2$, $b = 2$ ve sonucu belirleyen tek şey $f(n)$’dir.
• Aynı bölme üzerinde doğrusal birleştirme 2680 adımla kâhinin 1,16 katı azını harcıyor ve 40 girdide de doğru; karesel birleştirme 5320 adımla kâhinden 1,71 kat yavaş ama yine doğru.
• Sınırı geçen çözümü atlayan eksik birleştirme 920 adımla en ucuz olan ve 40 girdinin 40’ında yanlış; döndürdüğü şey dizinin en büyük tek elemanıdır.
• Bölme 8 elemana kadar kazandırmıyor; oran 1’i 8 ile 16 arasında geçiyor ve kayıp $2n - 1$ özyineleme çağrısından geliyor.
• Karesel birleştirmede oran hiçbir uzunlukta 1’i geçmiyor; ana teoremin üçüncü durumunda bölmenin $\log n$ kazancı ortadan kalkar.
• İkinci dağarcıkta doğrusal birleştirmenin adımı birebir aynı, eksik birleştirmenin ayrılan girdisi 40 yerine 39; aradaki bir girdilik fark çözünürlüğün altındadır.

Sonraki Adım

Böl ve yönet, problemi parçalayıp bütün parçaları çözüyordu. Sonraki kalıp bundan daha cesur bir şey yapar: her adımda tek bir seçim yapar ve geri dönmez. Bu cesaretin bazen kanıtı vardır — Algoritmalar kursundaki üç açgözlü yordamda olduğu gibi — bazen yoktur. Sonraki ders açgözlü seçimin ne zaman yanıldığını sayar: dört değerli para sistemlerinin kaçında açgözlü, gerekenden fazla para veriyor.