--- title: 'Böl ve Yönet' source: 'https://academia.sh/tr/kurslar/ileri-algoritmalar/bol-ve-yonet' course: 'İleri Algoritmalar ve Problem Çözme' language: tr updated: '2026-08-17T18:07:25+00:00' license: 'CC BY-SA 4.0' --- # Böl ve Yönet Bölme ile birleştirmenin ayrı hesaplar olduğu: aynı bölme üzerinde doğrusal birleştirme kâhinin 1,16 katı az adım harcayıp 40 girdide de doğru kalırken, karesel birleştirme kâhinden 1,71 kat yavaşlıyor ve sınırı geçen çözümü atlayan eksik birleştirme 920 adımla 40 girdinin 40'ında yanlış yanıt veriyor. Ö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. ```python # 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. ```python # 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. ```python # 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. ```python # 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 ```python # 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.