Bölüm 6: Böl ve Fethet Yaklaşımı

6.1Böl ve fethet paradigması

Bir algoritma tasarlarken iki şey düşünülür: problemin kendisi ve onu çözmek için izlenecek genel strateji. Strateji düzeyindeki kalıplara paradigma denir. Kaba kuvvet, açgözlü yaklaşım, dinamik programlama ve geri izleme böyle kalıplardır. Böl ve fethet bunların en eskilerinden ve en verimlilerinden biridir. Adı askerî bir deyimden gelir: büyük bir ordu bütün hâlinde yenilemiyorsa küçük birliklere ayrılır ve birlikler tek tek yenilir. Algoritmalarda “ordu” büyük problemdir, “birlikler” de onun küçük kopyalarıdır.

6.1.1Böl, parçala, yönet, birleştir

Yaklaşım dört adımla anlatılır. Ders kitaplarının çoğu yalnız üç adım sayar (böl, yönet, birleştir). Dört adımlı anlatım, bölmenin tek seferde değil, taban duruma kadar tekrar tekrar yapıldığını ayrıca vurgular:

1. Böl: Karmaşık problem daha küçük, yönetilebilir alt problemlere bölünür. Örneğin n öğeli bir dizi, n/2 öğeli iki yarıya ayrılır.
2. Parçala: Alt problemler, doğrudan çözülebilecek kadar küçülene dek bölünmeye devam eder. Bu tekrar özyinelemeyle sağlanır: alt probleme aynı fonksiyon uygulanır ve o fonksiyon da kendi girdisini böler.
3. Yönet: Her alt problem ayrı ayrı çözülür. Taban durumdaki alt problemler doğrudan, ötekiler özyinelemeli çağrıyla çözülür.
4. Birleştir: Alt problemlerin çözümleri birleştirilerek asıl problemin çözümü kurulur.

Şekil 6.1 bu akışı bir ağaç olarak gösterir. Ağacın kökü asıl problemdir. Her iç düğüm bir alt problemdir ve çocukları onun bölündüğü parçalardır. Yapraklar taban durumlardır. Algoritma yukarıdan aşağıya bölerek iner, aşağıdan yukarıya birleştirerek çıkar. Programda bu ağacın karşılığı özyineleme ağacıdır: her düğüm bir fonksiyon çağrısıdır.

Yaklaşımın işlemesi için alt problemlerin iki özelliği vardır. Birincisi, alt problem asıl problemle aynı türdendir; yalnız daha küçüktür. Bir diziyi sıralamak, yarısını sıralamakla aynı türden bir iştir. Bu yüzden aynı fonksiyon kendini çağırabilir ve ayrı bir “yarım dizi sıralama” fonksiyonu gerekmez. İkincisi, alt problemler birbirinden bağımsızdır. Sol yarıyı sıralamak sağ yarıyı sıralamaktan hiçbir bilgi istemez. Bu bağımsızlık bozulursa, yani alt problemler ortak alt alt problemler içerirse, aynı iş tekrar tekrar yapılır. Fibonacci özyinelemesi bunun en bilinen örneğidir.

6.1.2Neden böl ve fethet?

Böl ve fethet ilk bakışta yalnız bir düzenleme yöntemi gibi görünür: işi parçalara ayırıp parçaları tek tek yapmak. Oysa yaklaşımın asıl gücü, uygun problemlerde çalışma süresini mertebe olarak düşürebilmesidir. Bu notta ele alınan algoritmaların hemen hepsi, aynı problemi çözen saf yöntemden asimptotik olarak daha hızlıdır. Örnekler: sıralamada O(n²) yerine O(n log n), sıralı dizide aramada O(n) yerine O(log n), tam sayı çarpımında O(n²) yerine yaklaşık O(n^1,585).

Yaklaşımın başka yararları da vardır:

• Anlaşılırlık ve yeniden kullanım. Karmaşık problem küçük, yönetilebilir parçalara ayrılınca daha anlaşılır olur. Alt problemlerin çözüm yöntemi her düzeyde aynı fonksiyondur. Kod kısa kalır ve her düzeyde yeniden kullanılır.
• Paralellik. Alt problemler birbirinden bağımsız olduğu için farklı işlemci çekirdeklerinde aynı anda çözülebilir. Sol ve sağ yarının sıralanması birbirini beklemez.
• Bellek yerelliği. Alt problemler küçüldükçe önbelleğe sığar. Küçük bir alt dizi önbelleğe bir kez yüklenir ve üzerindeki bütün iş orada biter. Bu, büyük veride gözle görülür bir hız kazancı sağlar.
• Kolay doğruluk kanıtı. Özyinelemeli yapı, doğruluğun tümevarımla kanıtlanmasını doğal kılar: taban durum doğruysa ve birleştirme, doğru alt çözümlerden doğru çözüm kuruyorsa algoritma doğrudur.

Yaklaşımın bedelleri de bilinmelidir:

• Özyineleme yükü. Her çağrı çağrı yığınında bir çerçeve açar ve bunun zaman ve bellek maliyeti vardır. Bazı algoritmalar ek bellek de ister; örneğin birleştirme sıralaması O(n) ek dizi kullanır.
• Örtüşen alt problemler. Alt problemler bağımsız değilse aynı iş tekrar tekrar yapılır ve süre üstel olabilir.
• Küçük girdilerde sabit çarpanlar. Asimptotik kazanç büyük n'de görünür. Küçük n'de bölme, birleştirme ve çağrı yükü baskın çıkar. Bu yüzden pratikte bir eşik belirlenir; alt problem eşiğin altına düşünce basit bir yönteme geçilir. Karatsuba ve Strassen uygulamaları böyle çalışır.

Böl ve fethetin kullanıldığı alanlar geniştir. Sıralama ve arama, hesaplamalı geometri, büyük sayı ve matris aritmetiği bunların başında gelir. Hızlı Fourier dönüşümü ve oyun ağaçlarında arama da aynı kalıbı izler.

6.1.3Genel şablon

Böl ve fethet algoritmalarının hepsi aynı iskeleti izler. Aşağıdaki Java kodu bu iskeleti problemden bağımsız bir biçimde yazar. Problem ve Sonuc türleri, bol(), dogrudanCoz() ve birlestir() metotları her algoritmada başka bir anlam kazanır.

Sonuc bolVeFethet(Problem p) {
  if (p.boyut() <= ESIK)
    return dogrudanCoz(p);          // taban durumu
  Problem[] alt = bol(p);           // a alt problem, boyut n/b
  Sonuc[] cozum = new Sonuc[alt.length];
  for (int i = 0; i < alt.length; i++)
    cozum[i] = bolVeFethet(alt[i]); // yönet: özyineleme
  return birlestir(cozum);          // birleştir
}

Şablonun satırları paradigmanın adımlarıyla birebir eşleşir:

• if (p.boyut() <= ESIK) return dogrudanCoz(p); taban durumdur. Problem eşikten küçükse bölme durur ve problem doğrudan çözülür. Eşik çoğu zaman 1'dir: tek öğeli dizi zaten sıralıdır, tek öğenin en büyüğü kendisidir. Eşik daha büyük de seçilebilir; en yakın nokta çiftinde eşik 3'tür.
• Problem[] alt = bol(p); böl adımıdır. Problem a tane alt probleme ayrılır; her birinin boyutu n/b civarındadır.
• for döngüsü yönet adımıdır. Her alt problem için şablonun kendisi çağrılır. Parçala adımı ayrı bir satır değildir; bu özyinelemeli çağrının içinde, alt problemin yeniden bölünmesiyle gerçekleşir.
• return birlestir(cozum); birleştir adımıdır. Alt çözümler asıl çözüme dönüştürülür.

Şablonun çalışma süresi de aynı yapıdan okunur. T(n), n boyutlu problemi çözmenin süresi olsun. Algoritma a tane n/b boyutlu alt problemi özyinelemeyle çözer; bunların toplam süresi a · T(n/b)'dir. Bölme ve birleştirme için harcanan süre f(n) ile gösterilir. Böylece

T(n) = a · T(n/b) + f(n)

bağıntısı elde edilir. Bu bağıntıda a alt problem sayısı, n/b alt problem boyutu, f(n) de bölme ve birleştirme maliyetidir. Bağıntı, bir böl ve fethet algoritmasının maliyetini üç sayıyla özetler. Algoritmayı hızlandırmanın yolları da bu üç sayıdan okunur:

• Taban durum olmadan özyineleme bitmez. Bağıntı yalnız büyük n için geçerlidir; küçük n'de T(n) sabit bir değerdir. Taban durum unutulursa program sonsuz özyinelemeye girer ve StackOverflowError ile durur.
• Bölme dengeli olmalıdır. n/2 + n/2 biçimindeki bölme iyidir: problem her düzeyde yarıya iner ve yaklaşık log₂ n düzeyde taban duruma varılır. 1 + (n − 1) biçimindeki bölme kötüdür: problem her düzeyde yalnız bir öğe küçülür ve n düzey gerekir.
• Hız kazancı çoğu zaman a'yı azaltmaktan ya da f(n)'yi küçültmekten gelir. Karatsuba ve Strassen algoritmalarının bütün kazancı a'yı bir azaltmaktan gelir. Birleştirme maliyetini O(n log n)'den O(n)'ye indirmek de en yakın nokta çiftinde belirleyici olur.

6.1.4Şablonun uygulaması: en büyük öğe

Şablonu somut bir örnekte görmek için çok basit bir problem seçilir: bir dizinin en büyük öğesini bulmak. Bu problem tek bir döngüyle de çözülür; böl ve fethet burada süreyi kısaltmaz. Örneğin amacı, şablonun her parçasının koddaki karşılığını göstermektir.

Böl ve fethet düşüncesiyle problem şöyle kurulur. Dizinin en büyük öğesi, sol yarının en büyüğü ile sağ yarının en büyüğünden büyük olanıdır. Bu cümle problemi aynı türden iki küçük probleme indirger. Tek öğeli bir aralıkta en büyük öğe o öğenin kendisidir; bu da taban durumdur.

int enBuyuk(int[] a, int alt, int ust) {
  if (alt == ust) return a[alt];    // taban
  int orta = (alt + ust) / 2;
  int sol = enBuyuk(a, alt, orta);
  int sag = enBuyuk(a, orta + 1, ust);
  return Math.max(sol, sag);        // birleştir
}

Metot dizinin a[alt..ust] aralığıyla çalışır. Bütün dizi için enBuyuk(a, 0, n − 1) çağrılır. Satırların görevi şöyledir:

• if (alt == ust) return a[alt]; taban durumdur. Aralıkta tek öğe vardır ve en büyük öğe odur.
• int orta = (alt + ust) / 2; böl adımıdır. Aralık ortadan ikiye ayrılır: [alt..orta] ve [orta+1..ust]. Tam sayı bölmesi aşağı yuvarladığı için öğe sayısı tekse sol yarı bir öğe fazla alır.
• İki özyinelemeli çağrı yönet adımıdır: sol sol yarının, sag sağ yarının en büyüğüdür.
• return Math.max(sol, sag); birleştir adımıdır ve tek bir karşılaştırmadır.

Bölme yeni dizi oluşturmaz; yalnız iki indis hesaplar. Bu yüzden bölme ve birleştirme birlikte sabit sürelidir: f(n) = O(1). Bağıntı T(n) = 2T(n/2) + O(1) olur ve çözümü Θ(n)'dir.

6.1.5Kod izleme: enBuyuk(a, 0, 4)

İzlemede dizi a = [5, 2, 9, 4, 7]'dir ve enBuyuk(a, 0, 4) çağrılır. Aralıkta beş öğe vardır. Orta indis (0 + 4)/2 = 2'dir; sol yarı [0..2], sağ yarı [3..4] olur. Sol yarı üç öğe, sağ yarı iki öğe alır. Tablo 6.1 çağrıların sırasını ve her çağrının döndürdüğü değeri verir.

İzlemede çağrıların sırası dikkat ister. Bir çağrı, sol yarının işi tamamen bitmeden sağ yarıya geçmez. 3. adımda (0, 1) çağrısı başlar; 4. ve 5. adımda iki yaprağı çözer ve ancak 6. adımda sonucunu döndürür. Sağ yarı (3, 4) ise 9. adıma kadar hiç başlamaz. Bu sıra, özyineleme ağacının derinlik öncelikli gezilmesidir. Çağrı yığını hiçbir zaman ağacın yüksekliğinden fazla çerçeve tutmaz; burada en çok dört çerçeve vardır ((0,4), (0,2), (0,1) ve bir yaprak).

Sonuç 9'dur. Toplam çağrı sayısı 9'dur: 5 yaprak ve 4 iç düğüm. Yapılan karşılaştırma sayısı iç düğüm sayısına, yani 4'e eşittir. Genel olarak n öğeli dizide özyineleme ağacının n yaprağı vardır. Her iç düğümün tam iki çocuğu olduğu için iç düğüm sayısı n − 1'dir. Algoritma n − 1 karşılaştırma ve 2n − 1 çağrı yapar.

Basit bir döngü de diziyi baştan sona gezerek n − 1 karşılaştırmayla en büyük öğeyi bulur. Böl ve fethet karşılaştırma sayısını azaltmamıştır; üstelik çağrı yükü eklemiştir. O hâlde bu sürümün yararı nedir? Yanıt paralelliktir. İki yarı birbirinden bağımsızdır ve aynı anda çözülebilir. Sınırsız sayıda işlemci varsa ağacın her düzeyi tek adımda biter. Ağacın yüksekliği ⌈log₂ n⌉ olduğundan sonuç O(log n) paralel adımda bulunur. Döngüyle yazılan sürümde her karşılaştırma bir öncekinin sonucunu bekler ve bu zincir kısaltılamaz.

6.1.6Doğruluk ve tümevarım

Böl ve fethet algoritmalarının doğruluğu, özyinelemenin yapısını izleyen bir tümevarımla kanıtlanır. Tümevarım problem boyutu üzerinden yapılır. Önce taban durumda algoritmanın doğru olduğu gösterilir. Sonra daha küçük bütün girdilerde doğru olduğu kabul edilir ve birleştirme adımının doğru sonuç ürettiği gösterilir. enBuyuk için bu şöyle yapılır.

Kanıtta kullanılan alt ≤ orta < ust eşitsizliği önemlidir. Bölme, iki yarıdan birini boş ya da aralığın tamamı kadar bırakırsa tümevarım varsayımı kullanılamaz ve program sonsuz özyinelemeye girebilir. Örneğin orta yukarı yuvarlanıp sol yarı [alt..orta], sağ yarı [orta+1..ust] alınsaydı, iki öğeli aralıkta orta = ust olur ve sağ yarı boş kalırdı. Her böl ve fethet algoritmasında aynı soru sorulmalıdır: her alt problem gerçekten daha küçük müdür ve boş alt problem nasıl ele alınır?

6.2Özyineleme bağıntıları

Özyinelemeli bir algoritmanın süresi kendi cinsinden yazılır: n boyutlu problemin süresi, daha küçük problemlerin süreleri ve bölme ile birleştirme maliyeti cinsinden ifade edilir. Bu tür denkleme özyineleme bağıntısı (recurrence relation) denir. Bu kesim, bağıntıların kurulması ve ana teoremle çözülmesi hakkında böl ve fethet için gerekenleri kısaca hatırlatır.

6.2.1Bağıntıyı kurmak

Bağıntı, algoritmanın kodundan üç soru sorularak okunur:

1. Kaç özyinelemeli çağrı yapılıyor? Bu sayı a'dır. Burada yalnız gerçekten çalışan çağrılar sayılır. İkili arama iki ayrı çağrı satırı içerir, ama her yürütmede yalnız biri çalışır; bu yüzden a = 1'dir.
2. Her çağrının girdisi ne kadar? Girdi n/b ise b okunur. Girdi n − 1 gibi sabit miktarda küçülüyorsa bağıntı ana teoremin biçimine uymaz.
3. Çağrılar dışında ne kadar iş yapılıyor? Bölme ve birleştirmenin toplam maliyeti f(n)'dir. Döngüler, dizi kopyalama, alt liste oluşturma bu maliyete girer.

6.2.2Ana teorem

Ana teorem, T(n) = aT(n/b) + f(n) biçimindeki bağıntıları hesap yapmadan çözmeye yarar. Teorem, kökteki işi temsil eden f(n)'yi, yaprakların toplam işini temsil eden n^{log_b a} ile karşılaştırır. Bu ikinci değere kritik üs ya da yaprak işi denir: özyineleme ağacında log_b n düzey vardır ve her düzeyde düğüm sayısı a katına çıkar; yaprak sayısı a^{log_b n} = n^{log_b a}'dır.

Teoremin dili ilk bakışta ağırdır, ama kullanımı kısadır: f(n) ile n^{log_b a} karşılaştırılır; büyük olan kazanır; ikisi aynı mertebedeyse sonuca bir log n çarpanı eklenir. “Polinom olarak küçük” ifadesi, aradaki farkın en az n^ε gibi bir kuvvet olması demektir. Yalnız bir log n çarpanı kadar fark, polinom farkı sayılmaz.

6.2.3Özyineleme ağacında düzey toplamları

Ana teoremin üç durumu, özyineleme ağacının düzeylerindeki toplam işe bakılınca kendiliğinden anlaşılır. i. düzeyde aⁱ alt problem vardır ve her birinin boyutu n/bⁱ'dir. Bu düzeyde yapılan toplam iş aⁱ · f(n/bⁱ)'dir. Algoritmanın toplam süresi, bütün düzeylerin toplamıdır. Düzey toplamları kökten yapraklara doğru ya büyür, ya sabit kalır, ya da küçülür. Tablo 6.2 n = 16 için beş bağıntının düzey toplamlarını verir.

Tablo üç davranışı yan yana gösterir. İlk satırda her düzey aynı işi yapar: 16. Düzey sayısı log₂ n + 1 olduğundan toplam n log n mertebesindedir; bu durum 2'dir ve birleştirme sıralamasının bağıntısıdır. İkinci, üçüncü ve dördüncü satırlarda düzey toplamları geometrik olarak büyür. Geometrik dizide toplam, son terimin sabit katıdır; son terim de yaprak düzeyidir. 3T(n/2) + n için yaprak düzeyi 3⁴ = 81 = 16^{log₂ 3}'tür. Karatsuba bağıntısı budur ve süresi Θ(n^{log₂ 3})'tür. Son satırda düzey toplamları yarıya iner. Toplam bu kez ilk terimin, yani kökün sabit katıdır: Θ(n²).

Bu bakış, böl ve fethette hızlanmanın nereden geldiğini de açıklar. 4T(n/2) + n ile 3T(n/2) + n arasındaki tek fark, her düzeyde bir alt problemin eksik olmasıdır. Ama bu fark her düzeyde katlanır: n = 16'da yaprak düzeyinde 256 yerine 81 iş kalır. n büyüdükçe oran (4/3)^{log₂ n} = n^{2 − 1,585} gibi büyür.

6.2.4Bu bölümün algoritmaları ve ana teorem

Tablo 6.3 bu notta ele alınan algoritmaların bağıntılarını ana teoremle çözer. Hesapların ortak yanı, a, b ve f(n)'nin koddan okunması ve kritik üssün f(n)'nin üssüyle karşılaştırılmasıdır.

Tablonun son üç satırı ortak bir ders taşır. Karatsuba ve Strassen'in bütün kazancı a'yı bir azaltmaktan gelir: 4'ten 3'e ve 8'den 7'ye. Bölme ve birleştirme maliyeti f(n) değişmez, hatta biraz artar. Durum 1'de süre yalnız kritik üsse bağlıdır ve kritik üs log_b a'dır. a küçülünce üs de küçülür: log₂ 4 = 2 iken log₂ 3 ≈ 1,585; log₂ 8 = 3 iken log₂ 7 ≈ 2,807.

6.2.5Ana teoremin uygulanamadığı bağıntılar

Ana teorem güçlüdür ama dar bir kalıba uyar: bütün alt problemler aynı boyutta olmalı ve boyut bir oranla küçülmelidir. Böl ve fethet algoritmalarının bir kısmı bu kalıba uymaz:

• Sabit miktarda küçülme. T(n) = T(n − 1) + n bağıntısında b yoktur. Dengesiz hızlı sıralama ve en kötü durumdaki Quickhull böyle davranır. Bağıntı açılınca n + (n − 1) + … + 1 = n(n + 1)/2 = Θ(n²) bulunur.
• Eşit olmayan bölmeler. Quickhull'un bağıntısı T(n) = T(n₁) + T(n₂) + O(n)'dir ve n₁, n₂ girdiye göre değişir. T(n) = T(n/3) + T(2n/3) + n gibi sabit oranlı ama eşit olmayan bölmeler de teoremin dışında kalır. Bunlar özyineleme ağacıyla çözülür: son örnekte her düzeyin toplamı en çok n'dir ve en uzun dal log_3/2 n düzeydir; sonuç Θ(n log n)'dir.
• Durumlar arasında kalan f(n). T(n) = 2T(n/2) + n/log n'de f(n) = n/log n, n'den küçüktür ama polinom olarak küçük değildir: fark yalnız bir log n çarpanıdır. Teoremin hiçbir durumu uygulanmaz. Benzer biçimde en yakın nokta çiftinin hatalı sürümündeki 2T(n/2) + n log n bağıntısı da ana teoremin üç durumunun dışındadır; çözümü Θ(n log² n)'dir.

6.3Temel örnekler

Birleştirme sıralaması, hızlı sıralama ve ikili arama tanıdık algoritmalardır. Bu kesim onları yeniden anlatmaz; yalnız aynı paradigmanın üç farklı yüzü olarak yan yana koyar. Ardından iki yeni örnek gelir: üs almayı logaritmik zamana indiren hızlı üs alma ve böl ve fethetin kötü sonuç verdiği Fibonacci özyinelemesi.

6.3.1Klasik böl ve fethet algoritmaları

Tablo 6.4 bu notta adı geçen algoritmaların böl ve birleştir adımlarını ve bağıntılarını tek tabloda toplar. Tabloya satır satır değil, sütun sütun bakmak öğreticidir. “Birleştir” sütununda üç algoritmanın karşısında “yok” yazar: ikili aramada, hızlı sıralamada ve hızlı üs almada iş ya bölme anında yapılır ya da sonuç tek bir alt problemden doğrudan gelir.

6.3.2Birleştirme sıralaması: iş birleştirmede

Birleştirme sıralaması böl ve fethetin en düz örneğidir. Böl adımı diziyi ortadan ikiye ayırır ve yalnız bir orta indis hesapladığı için O(1) sürer. Yönet adımında iki yarı özyinelemeyle sıralanır. Birleştir adımında iki sıralı yarı, her adımda iki yarının başındaki küçük öğe alınarak tek geçişte birleştirilir; bu adım Θ(n) sürer.

Şekil 6.3 yedi öğeli bir dizinin sıralanmasını düzey düzey gösterir. Önce orta = (0 + 6)/2 = 3 ile dizi [38 27 43 3] ve [9 82 10] yarılarına ayrılır. Yarılar yeniden bölünür: [38 27], [43 3], [9 82], [10]. Tek öğeli diziler zaten sıralıdır ve taban durumdur. Birleştirme aşağıdan yukarıya çalışır. Önce ikililer [27 38], [3 43], [9 82] olur. Sonra [3 27 38 43] ve [9 10 82] elde edilir; en son bu ikisi [3 9 10 27 38 43 82]'yi verir. Her birleştirme, iki yarının uzunlukları toplamı kadar adım sürer. Bir düzeydeki bütün birleştirmeler birlikte en çok n öğeye dokunur. Düzey sayısı ⌈log₂ 7⌉ = 3'tür.

Bağıntı T(n) = 2T(n/2) + Θ(n)'dir ve ana teoremin 2. durumuna girer: Θ(n log n). Bölme girdiye bakmadan hep ortadan yapıldığı için bu süre en iyi, ortalama ve en kötü durumda aynıdır. Paradigma açısından en önemli gözlem şudur: asıl iş birleştirmede yapılır. Karşılaştırmaların hepsi birleştirme döngüsündedir; bölme hiçbir öğeye bakmaz.

6.3.3Hızlı sıralama: iş bölmede

Hızlı sıralama aynı problemi ters yönden çözer. Böl adımı, bir pivot öğe seçip diziyi pivottan küçükler ve büyükler olarak iki tarafa ayırır. Bu işleme parçalama (partition) denir ve Θ(n) sürer. Yönet adımında iki parça özyinelemeyle sıralanır. Birleştir adımı yoktur: parçalar yerinde sıralandığı için iki sıralı parça zaten doğru sırada yan yana durur. Birleştirme sıralamasının tersine asıl iş bölmede yapılır.

Şekil 6.4'deki örnekte Lomuto parçalaması kullanılır: aralığın son öğesi pivottur. Tablo 6.5 çağrıların sırasını verir.

İlk parçalama dengeli sayılabilir: dört ve iki öğelik parçalar oluşur. Ama sol parça [10 30 40 50] zaten sıralıdır. Son öğe pivot olduğu için her parçalama yalnız bir öğeyi ayırır. Pivot 50, 40 ve 30 sırayla sona yerleşir; sağ parça her seferinde boş kalır. Bu, böl ve fethetin en kötü bölmesidir: 1 + (n − 1).

Hızlı sıralamanın süresi bölmenin dengesine bağlıdır. Pivot ortanca civarındaysa bağıntı T(n) = 2T(n/2) + O(n) olur ve süre O(n log n)'dir; ortalama durum budur. Sıralı girişte son öğe pivot seçilirse her parçalama bir öğe ayırır; bağıntı T(n) = T(n − 1) + O(n), süre O(n²) olur. Çare, pivotu girdiden bağımsız seçmektir: rastgele pivot ya da ilk, orta ve son öğenin ortancası.

İki sıralama algoritmasının karşılaştırması paradigmanın esnekliğini gösterir. İşin bir yerde yapılması kaçınılmazdır. Hızlı sıralama önce akıllıca böler ve birleştirme bedavaya gelir. Birleştirme sıralaması körü körüne böler ve akıllıca birleştirir. Birleştirme sıralaması dengeyi garanti eder ama ek dizi ister; hızlı sıralama yerinde çalışır ama dengeyi pivot seçimine bırakır.

6.3.4İkili arama: azalt ve fethet

Sıralı bir dizide ikili arama, ortadaki öğeyi aranan değerle karşılaştırır ve dizinin bir yarısını tamamen atar. Arama yalnız kalan yarıda sürer. Bağıntı T(n) = T(n/2) + O(1)'dir; a = 1, b = 2, n^{log₂ 1} = n⁰ = 1 ve f(n) = 1 aynı mertebededir. Durum 2'den Θ(log n) çıkar. Bir milyon öğeli dizide en çok 20 yoklama yeter.

İkili aramada tek bir alt problem vardır ve birleştirme yoktur. Bu yüzden bazı kaynaklar ona böl ve fethet değil, azalt ve fethet (decrease and conquer) adını verir: problem bölünmez, yalnız küçültülür. Ayrım terminolojiktir; analiz aynı bağıntıyla yapılır. Asıl gözlem şudur: alt problemlerden biri atılabiliyorsa kazanç büyüktür. Doğrusal arama O(n), ikili arama O(log n) sürer.

6.3.5Hızlı üs alma

xⁿ'yi hesaplamanın saf yolu x'i kendisiyle n − 1 kez çarpmaktır. n = 10⁶ için bu 999 999 çarpım demektir. Böl ve fethet ile çok daha az çarpım yeter. Gözlem basittir:

xⁿ = (x^n/2)² (n çift),   xⁿ = x · (x^⌊n/2⌋)² (n tek).

Örneğin 3¹³ = 3 · (3⁶)², 3⁶ = (3³)², 3³ = 3 · (3¹)²'dir. xⁿ problemi, üssü yarı olan tek bir alt probleme indirgenir. Alt problemin sonucu bir kez hesaplanır ve kendisiyle çarpılır. Taban durum x⁰ = 1'dir.

long us(long x, int n) {
  if (n == 0) return 1;         // taban
  long y = us(x, n / 2);
  if (n % 2 == 0) return y * y; // çift
  return x * y * y;             // tek
}

Kodun en önemli satırı long y = us(x, n / 2);'dir. Yarım üssün değeri bir değişkende saklanır ve iki kez kullanılır: çift n'de y * y, tek n'de x * y * y döndürülür. Böylece her çağrı yalnız bir özyinelemeli çağrı yapar ve en çok iki çarpma ekler. Bağıntı T(n) = T(n/2) + O(1)'dir ve sonuç O(log n)'dir. Çağrı sayısı, n'nin ikili yazımındaki basamak sayısından bir fazladır; çarpım sayısı en çok 2(⌊log₂ n⌋ + 1)'dir.

6.3.6Kod izleme: us(3, 13)

us(3, 13) çağrıldığında üs her çağrıda yarıya iner: 13 → 6 → 3 → 1 → 0. Çağrılar önce bu zincir boyunca iner, sonra değerler geri dönerken çarpmalar yapılır. Tablo 6.6 dönüş sırasını verir.

Toplam çarpım sayısı 2 + 2 + 1 + 2 = 7'dir; saf yöntem 12 çarpım yapardı. Fark küçük üslerde azdır, büyük üslerde çarpıcıdır. n = 10⁶'da hızlı üs alma 21 çağrı ve 27 çarpım yapar; saf yöntem 999 999 çarpım yapar.

Bir uyarı: long türü en çok 2⁶³ − 1 ≈ 9,22 · 10¹⁸ değerini tutar. 3³⁹ ≈ 4,05 · 10¹⁸ sığar, ama 3⁴⁰ ≈ 1,22 · 10¹⁹ sığmaz ve Java hata vermeden taşar. Gerçek uygulamalarda hızlı üs alma ya BigInteger ile ya da her çarpımdan sonra bir modüle göre kalan alınarak (xⁿ mod m) kullanılır. İkinci biçim, açık anahtarlı şifrelemede çok büyük üslerin hesaplanmasının temelidir.

6.3.7Uygun olmayan durum: örtüşen alt problemler

Fibonacci sayıları F(0) = 0, F(1) = 1 ve F(n) = F(n − 1) + F(n − 2) ile tanımlanır. Tanım özyinelemelidir ve doğrudan koda dökülebilir:

long fib(int n) {
  if (n < 2) return n;
  return fib(n - 1) + fib(n - 2);
}

Kod böl ve fethet biçimindedir: problem iki küçük alt probleme ayrılır, alt problemler aynı fonksiyonla çözülür ve sonuçlar toplanarak birleştirilir. Sonuç da doğrudur. Ama bu kötü bir örnektir, çünkü alt problemler birbirinden bağımsız değildir. F(n − 1)'i hesaplamak için F(n − 2) zaten hesaplanır; sonra F(n − 2) ikinci çağrıda baştan hesaplanır.

Şekil 6.6'deki ağaçta fib(5) için 15 çağrı yapılır. F(3) iki kez, F(2) üç kez, F(1) beş kez, F(0) üç kez hesaplanır. Çağrı sayısı C(n) = 2F(n + 1) − 1 formülüyle büyür: fib(30) için 2 692 537, fib(40) için 331 160 281 çağrı yapılır. Bağıntı T(n) = T(n − 1) + T(n − 2) + O(1)'dir ve çözümü O(φⁿ)'dir; burada φ = (1 + √5)/2 ≈ 1,618 altın orandır.

Çözüm, her alt problemin sonucunu ilk hesaplandığında saklamak ve ikinci kez gerektiğinde tablodan okumaktır. Bu yaklaşımın adı dinamik programlamadır; Fibonacci için süreyi O(n)'ye indirir. Paradigma seçiminde sorulacak soru şudur: alt problemler birbirinden bağımsız mı, yoksa ortak alt alt problemler mi içeriyor? Bağımsızsa böl ve fethet, örtüşüyorsa dinamik programlama uygundur. Her adımda yerel olarak en iyi seçim küresel en iyiye götürüyorsa açgözlü yaklaşım daha da basit bir çözüm verir.

6.4Dışbükey örtü ve Quickhull

Hesaplamalı geometri, noktalar, doğrular ve çokgenler üzerinde çalışan algoritmaları inceler. Bu alanın en temel problemlerinden biri dışbükey örtüdür. Problemin böl ve fethetle çözümü olan Quickhull, adını hızlı sıralamaya benzerliğinden alır: bir “pivot” seçilir, noktalar bu pivota göre parçalanır ve parçalar özyinelemeyle işlenir.

6.4.1Dışbükey örtü problemi

Tanımı akılda tutmanın kolay bir yolu vardır. Noktaların yerine bir tahtaya çiviler çakıldığı ve bütün çivilerin çevresine bir lastik bant geçirildiği düşünülsün. Bant bırakılınca dıştaki çivilere sarılır ve gerilir. Bandın aldığı şekil dışbükey örtüdür. Bu benzetme iki önemli gerçeği de gösterir. Birincisi, örtünün köşeleri S'nin noktalarıdır; bant yalnız çivilere değer. İkincisi, içteki çiviler bandın biçimini hiç etkilemez.

Algoritmanın çıktısı, örtünün köşelerinin sıralı listesidir; geleneksel olarak saat yönünün tersine sıralanır. Yalnız “hangi noktalar örtüdedir?” sorusunu yanıtlamak yetmez, çünkü çokgeni çizmek ya da üzerinde hesap yapmak için köşelerin sırası gerekir. Şekil 6.7'deki kümenin örtüsü yedi köşelidir; kalan dokuz nokta içeridedir.

Dışbükey örtü pek çok uygulamanın ilk adımıdır. Oyunlarda ve robotikte çarpışma algılama, karmaşık bir nesnenin yerine onun örtüsünü kullanarak hızlanır: iki örtü kesişmiyorsa nesneler de kesişmez. Coğrafi bilgi sistemleri bir bölgedeki gözlem noktalarının sınırını örtüyle çizer. Görüntü işlemede bir şeklin örtüsü onun biçimini özetler. Bir kümenin birbirinden en uzak iki noktası mutlaka örtünün köşeleridir; bu gözlem en uzak nokta çifti problemini küçültür. Kümelemede her kümenin sınırı örtüyle gösterilir.

6.4.2Quickhull algoritması

Quickhull şu gözleme dayanır: bir doğruya en uzak nokta, o doğrunun o tarafındaki noktaların örtüsünde mutlaka yer alır. Algoritma şu adımlarla çalışır:

1. x koordinatı en küçük nokta A ve en büyük nokta B bulunur. İkisi de örtüdedir: en soldaki ve en sağdaki noktalar hiçbir zaman başka noktaların arasında kalamaz.
2. AB doğrusu noktaları iki alt kümeye ayırır: doğrunun üstü (A'dan B'ye bakarken solu) ve altı (sağı).
3. Bir alt kümede AB'ye en uzak C noktası bulunur. C örtüdedir.
4. ACB üçgeninin içindeki noktalar elenir: üçgenin köşeleri örtüde olduğuna göre üçgenin içi de örtünün içindedir ve bu noktalar örtünün köşesi olamaz.
5. AC'nin dışında kalanlar ve CB'nin dışında kalanlar için aynı işlem özyinelemeyle yapılır.
6. Bir kenarın dışında hiç nokta kalmayınca o kenar bir örtü kenarıdır ve özyineleme durur. Bulunan noktalar örtüyü oluşturur.

Hızlı sıralamayla benzerlik açıktır. Hızlı sıralamada pivot diziyi iki parçaya ayırır; Quickhull'da en uzak nokta C, üçgenin iki kenarına göre kümeyi iki parçaya ayırır. Bir fark vardır: Quickhull'da parçalamada bazı noktalar hiçbir parçaya girmez. Üçgenin içindeki noktalar tamamen atılır ve bu atma, algoritmanın pratikte hızlı olmasının asıl nedenidir.

Algoritmada birleştirme adımı neredeyse yoktur. Her özyinelemeli çağrı bulduğu noktayı örtü listesine ekler; iki alt çağrının sonuçları ayrıca birleştirilmez. İş, hızlı sıralamada olduğu gibi bölme anında yapılır: en uzak noktayı bulmak ve noktaları üçgenin kenarlarına göre ayırmak.

6.4.3Yönelim testi ve uzaklık

Algoritma iki geometrik soruyu sürekli sorar: bir P noktası A → B doğrusunun solunda mı, sağında mı? Ve P'nin AB'ye uzaklığı ne kadar? İki soru da tek bir formülle yanıtlanır. Formül yalnız tam sayı çarpımı ve çıkarması kullanır; açı, karekök ya da bölme gerekmez.

long capraz(Nokta A, Nokta B, Nokta P) {
  return (long)(B.x - A.x) * (P.y - A.y)
       - (long)(B.y - A.y) * (P.x - A.x);
}

capraz metodu, A → B ve A → P vektörlerinin çapraz çarpımının (vektörel çarpımının) z bileşenini hesaplar. (long) dönüşümleri, büyük koordinatlarda int çarpımının taşmasını önler. Değerin işareti yönü verir:

• capraz > 0: P, A → B'nin solundadır (saat yönünün tersine dönüş).
• capraz < 0: P, A → B'nin sağındadır (saat yönünde dönüş).
• capraz = 0: A, B, P aynı doğru üzerindedir.

Değerin mutlak büyüklüğü de anlam taşır. |capraz|, A, B ve P köşeli üçgenin alanının iki katıdır. Üçgenin alanı ayrıca ½ · |AB| · h'dir; burada h, P'nin AB doğrusuna dik uzaklığıdır. Buradan |capraz| = |AB| · h çıkar. Aynı A ve B için |AB| sabittir. Bu yüzden doğruya en uzak nokta, capraz değeri en büyük olan noktadır ve uzaklığı ayrıca hesaplamaya gerek yoktur.

6.4.4Kod: quickHull() ve bul()

void quickHull(List<Nokta> P) {
  Nokta A = enSol(P), B = enSag(P);
  ortu.add(A); ortu.add(B);
  bul(solda(P, A, B), A, B); // üst küme
  bul(solda(P, B, A), B, A); // alt küme
}
void bul(List<Nokta> S, Nokta A, Nokta B) {
  if (S.isEmpty()) return;   // AB örtü kenarı
  Nokta C = enUzak(S, A, B); // max capraz
  ortu.add(C);
  bul(solda(S, A, C), A, C); // AC'nin dışı
  bul(solda(S, C, B), C, B); // CB'nin dışı
}  // ACB üçgeninin içi elenir

Kod iki metottan oluşur. quickHull başlatıcıdır: en sol ve en sağ noktayı bulur, onları örtüye ekler ve iki yarı için bul'u çağırır. bul(S, A, B), A → B doğrusunun solunda kalan S kümesiyle çalışır ve bu kümedeki örtü köşelerini bulur:

• if (S.isEmpty()) return; taban durumdur. Doğrunun dışında hiç nokta yoksa AB bir örtü kenarıdır.
• Nokta C = enUzak(S, A, B); en büyük capraz değerli noktayı seçer ve ortu.add(C); onu örtüye ekler.
• İki özyinelemeli çağrı, A → C'nin solunda ve C → B'nin solunda kalan noktalarla çalışır. Bu iki kümeden hiçbirine girmeyen noktalar üçgenin içindedir ve kendiliğinden elenir; onlar için ayrı bir kod yoktur.

Alt kümenin B → A yönüyle işlenmesi bir incelik içerir. Doğrunun altı, A → B'nin sağı, yani B → A'nın soludur. Bu sayede bul her zaman “doğrunun solundaki noktalar” sözleşmesiyle çalışır ve tek bir metot iki tarafa da yeter. Kodda kullanılan yardımcı metotlar aşağıdadır. enSol ve enSag listeyi bir kez tarayıp x'i en küçük ve en büyük noktayı döndürür.

List<Nokta> solda(List<Nokta> S, Nokta A, Nokta B) {
  List<Nokta> sonuc = new ArrayList<>();
  for (Nokta p : S)
    if (capraz(A, B, p) > 0) sonuc.add(p); // A→B'nin solunda
  return sonuc;
}
Nokta enUzak(List<Nokta> S, Nokta A, Nokta B) {
  Nokta enIyi = null;
  long enBuyukDeger = -1;
  for (Nokta p : S) {
    long c = capraz(A, B, p);
    if (c > enBuyukDeger) { enBuyukDeger = c; enIyi = p; }
  }
  return enIyi;
}

solda ve enUzak listeyi birer kez tarar; ikisi de O(|S|) sürer. Bir bul çağrısı bu yüzden kendi kümesinin boyuyla orantılı iş yapar: bir enUzak ve iki solda taraması.

ortu listesi köşeleri bulunma sırasıyla tutar ve bu sıra çokgenin çevresindeki sıra değildir. Sıralı çıktı için ortu.add(C) satırını iki özyinelemeli çağrının arasına taşımak yeter. Bu durumda üst kümede köşeler A'dan B'ye, alt kümede B'den A'ya doğru eklenir; A en başa, B iki kümenin arasına yazılırsa köşeler saat yönünde sıralanır. Liste ters çevrilince saat yönünün tersine sıra elde edilir.

6.4.5Kod izleme: 16 nokta

İzlemede Şekil 6.7'deki 16 nokta kullanılır: (2,18), (4,25), (10,5), (11,16), (13,27), (14,19), (16,12), (20,16), (20,2), (21,12), (23,20), (24,15), (27,9), (27,15), (28,23), (35,11). En sol nokta A = (2, 18), en sağ nokta B = (35, 11)'dir ve ikisi örtüye eklenir. Kalan 14 noktanın 8'i A → B'nin solunda (üst küme), 6'sı sağındadır (alt küme). Tablo 6.7 bul çağrılarını sırayla verir.

Tablonun ilk satırı algoritmanın en verimli anıdır. Üst kümenin 8 noktasından en uzak olanı C = (13, 27)'dir; capraz değeri 374'tür. Üçgenin içinde kalan dört nokta, (14,19), (20,16), (24,15) ve (27,15), tek hamlede elenir. AC'nin dışında yalnız (4,25), CB'nin dışında (23,20) ve (28,23) kalır. Sayılar tutarlıdır: 8 = 1 + 4 + 1 + 2 (C, elenenler ve iki dış küme).

2. çağrıda tek noktalı küme işlenir. Tek nokta doğal olarak en uzak noktadır: (4,25) örtüye girer ve iki alt çağrı boş kümeyle döner. 5. çağrıda iki nokta vardır: (13,27) → (35,11) doğrusuna (28,23) daha uzaktır (capraz = 152); (23,20) üçgenin içinde kalır ve elenir. Alt kümede 8. çağrı C = (20, 2)'yi seçer (capraz = 402) ve (11,16), (16,12), (21,12), (27,9) noktalarını eler. Kalan tek nokta (10,5), 10. çağrıda örtüye girer.

İzleme sonunda örtü yedi köşelidir: (2,18), (35,11), (13,27), (4,25), (28,23), (20,2), (10,5). Dokuz nokta elenmiştir ve toplam 12 bul çağrısı yapılmıştır. Çağrı sayısı yapı gereği bellidir: örtüye bul içinde eklenen her köşe iki alt çağrı açar ve her örtü kenarı bir boş çağrıyla biter. Burada 5 köşe bul içinde bulunmuş (5 dolu çağrı) ve örtünün 7 kenarı 7 boş çağrı vermiştir.

6.4.6104 noktalı örnek

Algoritmanın gücü büyük kümelerde daha açık görünür. 104 noktalı bir kümede en sol nokta (−14, 46), en sağ nokta (106, 20)'dir. Bu iki noktayı birleştiren doğrunun üstünde 71, altında 31 nokta vardır. Tablo 6.8 yalnız dolu çağrıları, yani örtüye nokta ekleyen çağrıları verir. “Aday” sütunu, henüz ne örtüye eklenmiş ne de elenmiş nokta sayısıdır; başta 71 + 31 = 102'dir.

İlk çağrı tek başına 56 noktayı, alt kümedeki ilk çağrı 25 noktayı eler. Elenen 94 noktanın 81'i bu iki çağrıdan gelir. Sonraki çağrıların kümeleri küçüktür: 6, 2, 8, 1, 5 nokta. Toplam 8 dolu çağrıyla örtünün 10 köşesi bulunur ve 94 nokta elenir. Her adımda noktaların çoğu elendiği için iş hızla azalır. Düzgün dağılmış rastgele noktalarda bu durum tipiktir: örtünün köşe sayısı n'ye göre çok küçüktür ve noktaların büyük çoğunluğu ilk birkaç üçgenin içine düşer.

6.4.7Analiz ve diğer örtü algoritmaları

Her bul çağrısı kendi kümesini sabit sayıda tarar: en uzak noktayı bulmak için bir kez, iki dış kümeyi ayırmak için iki kez. Çağrının işi O(|S|)'dir. Bağıntı

T(n) = T(n₁) + T(n₂) + O(n),   n₁ + n₂ ≤ n − 1

biçimindedir. n₁ ve n₂ girdiye bağlıdır; bu yüzden ana teorem uygulanamaz ve durumlar ayrı ayrı incelenir:

• Ortalama durum. Bölmeler dengeliyse ve her adımda çok nokta eleniyorsa süre O(n log n)'dir. Düzlemde düzgün dağılmış rastgele noktalarda algoritma çoğu zaman bundan da hızlıdır, çünkü elenen noktalar özyinelemenin derinlerine hiç inmez.
• En kötü durum. Her adımda en uzak nokta yalnız bir noktayı ayırabilir. Örneğin noktalar dışbükey bir eğri üzerinde dizilmiş ve en uzak nokta hep bir uca komşu düşüyor olabilir. Bu durumda bağıntı T(n) = T(n − 1) + O(n) olur ve süre O(n²)'dir. Bu girdide hiçbir nokta elenmez; bütün noktalar örtüdedir.
• Çıktıya duyarlı sınır. Örtünün köşe sayısı h olsun. Özyineleme ağacının bir düzeyindeki kümeler ayrıktır; bu yüzden bir düzeyin toplam işi en çok n'dir. Kökten yaprağa giden her yoldaki dolu çağrılar farklı köşeler bulduğu için ağacın derinliği h'yi aşmaz. Toplam iş O(n · h)'dir. Köşe sayısı küçükse bu sınır n log n'den bile iyidir.

Dışbükey örtü için başka algoritmalar da vardır. Tablo 6.9 bunları süreleriyle karşılaştırır.

Bu sürelerin altına inmek mümkün değildir. Dışbükey örtü bulan bir algoritma sıralama problemini de çözebilir: sıralanacak x₁, …, x_n sayıları y = x² parabolü üzerine (x_i, x_i²) noktaları olarak yerleştirilir. Parabol dışbükey olduğu için bütün noktalar örtünün köşesidir ve örtünün sıralı köşe listesi, sayıları sıralı olarak verir. Karşılaştırmalı modelde sıralama Ω(n log n) zaman gerektirdiğine göre, dışbükey örtü de en az bu kadar zaman gerektirir. Graham ve Andrew algoritmaları bu anlamda en iyidir. Chan algoritmasının O(n log h) süresi bu alt sınırla çelişmez, çünkü parabol örneğinde h = n'dir.

6.5En yakın nokta çifti

Düzlemdeki noktalar arasında birbirine en yakın iki noktayı bulmak, hesaplamalı geometrinin en eski problemlerinden biridir. Kaba kuvvet çözümü bütün çiftlere bakar ve karesel süre alır. Böl ve fethet çözümü ise süreyi O(n log n)'ye indirir. Çözümün ilginç yanı birleştirme adımıdır: iki yarının sınırında kalan çiftleri kaçırmamak için geometrik bir gözlem gerekir.

6.5.1Problem ve kaba kuvvet

Problem pek çok uygulamada ortaya çıkar. Hava trafiği kontrolünde birbirine en çok yaklaşan iki uçak sürekli izlenir. Kümeleme algoritmaları en yakın iki noktayı ya da kümeyi birleştirerek ilerler. Çarpışma algılamada birbirine en yakın iki nesne ilk aday çifttir. Coğrafi verilerde birbirine yakın tesisler bulunur.

En doğrudan çözüm bütün çiftlerin uzaklığını hesaplayıp en küçüğünü almaktır:

double kabaKuvvet(List<Nokta> p) {
  double enAz = Double.MAX_VALUE;
  for (int i = 0; i < p.size(); i++)
    for (int j = i + 1; j < p.size(); j++)
      enAz = Math.min(enAz, mesafe(p.get(i), p.get(j)));
  return enAz;
}

İç içe iki döngü her çifti bir kez dener: j her zaman i'den büyüktür, böylece hem (p, q) hem (q, p) denenmez, bir nokta kendisiyle de karşılaştırılmaz. Çift sayısı n(n − 1)/2'dir ve süre O(n²)'dir. 10 nokta için 45 uzaklık hesaplanır; n = 10⁶ için yaklaşık 5 · 10¹¹ uzaklık gerekir. Modern bir bilgisayarda bu, dakikalar süren bir iştir.

Tek boyutta problem kolaydır. Sayılar sıralanır ve yalnız ardışık sayılar karşılaştırılır: en yakın iki sayı, sıralı dizide mutlaka yan yanadır. Süre sıralamanın süresidir: O(n log n). İki boyutta bu fikir doğrudan çalışmaz. Noktalar x'e göre sıralandığında x'leri yakın iki nokta, y'leri çok farklı olduğu için birbirinden uzak olabilir. x'e göre sıralı dizide yan yana olmayan iki nokta da en yakın çift olabilir. Böl ve fethet bu güçlüğü aşar.

6.5.2Böl ve fethet: orta şerit

Algoritma şu adımlarla çalışır:

1. Noktalar bir kez x'e, bir kez y'ye göre sıralanır. Bu iki sıralı liste X ve Y olarak adlandırılır. Sıralama yalnız başta, özyinelemeden önce yapılır.
2. Böl: X'in ortasındaki noktanın x koordinatından geçen dikey L doğrusu, noktaları sol ve sağ iki yarıya ayırır.
3. Yönet: İki yarıda en yakın uzaklık özyinelemeyle bulunur: δ_L ve δ_R. İkisinin küçüğü δ = min(δ_L, δ_R)'dir.
4. Birleştir: Daha yakın bir çift hâlâ olabilir: bir noktası solda, öbürü sağda olan bir çift. Böyle bir çift varsa L'yi keser ve iki noktası da L'ye δ'dan yakındır. Bu yüzden yalnız |x − L| < δ olan noktalara, yani 2δ genişliğindeki şerit noktalarına bakılır.
5. Şerit y sırasıyla taranır. Her nokta yalnız kendisinden sonra gelen ve y farkı δ'dan küçük olan noktalarla karşılaştırılır.

Birleştirme adımının gerekçesi şudur. İki noktası da aynı yarıda olan çiftler özyinelemede zaten incelenmiştir ve hiçbiri δ'dan yakın değildir. Geriye yalnız L'yi kesen çiftler kalır. Böyle bir çiftin uzaklığı δ'dan küçükse x farkı da δ'dan küçüktür; bu yüzden iki noktası da L'nin en çok δ uzağındadır. Benzer biçimde y farkı da δ'dan küçük olmalıdır. Şeridi y sırasıyla taramak, bu ikinci koşulu ucuza denetlemenin yoludur: y farkı δ'yı aştığı anda sonraki noktalar daha da uzaktır ve iç döngü durur.

6.5.3Şeritte neden en çok yedi komşu?

Şerit kalabalık olabilir. Kötü bir girdide noktaların hepsi şeride düşebilir. Şerit noktalarının her çiftini denemek yine karesel süre alırdı. Algoritmayı hızlı yapan gözlem, şeritteki her noktanın yalnız sabit sayıda komşusuyla karşılaştırılmasının yetmesidir.

Teorem sınırı verir; kod bu sınırı açıkça yazmaz. İç döngü y farkı δ'yı aşınca durur. Teorem, bu koşul altında iç döngünün en çok 7 tur döndüğünü garanti eder. Bazı kaynaklar sınırı 6 ya da 5'e kadar indirir; sabitin değeri süre mertebesini değiştirmez. Önemli olan, şerit taramasının O(7n) = O(n) sürmesidir.

6.5.4Kod: enYakin()

double enYakin(List<Nokta> X, List<Nokta> Y) {
  int n = X.size(), orta = n / 2;
  if (n <= 3) return kabaKuvvet(X);
  Nokta m = X.get(orta); // Ysol/Ysag: Y'nin yarıları
  double dSol = enYakin(X.subList(0, orta), Ysol);
  double dSag = enYakin(X.subList(orta, n), Ysag);
  double d = Math.min(dSol, dSag);
  List<Nokta> s = new ArrayList<>();  // şerit
  for (Nokta p : Y)                   // y sırası
    if (Math.abs(p.x - m.x) < d) s.add(p);
  for (int i = 0; i < s.size(); i++) {
    Nokta p = s.get(i);
    for (int j = i + 1; j < s.size()
         && s.get(j).y - p.y < d; j++)
      d = Math.min(d, mesafe(p, s.get(j)));
  }
  return d;
}

Metot iki liste alır: X, noktaların x'e göre sıralı listesi, Y de aynı noktaların y'ye göre sıralı listesidir. İlk çağrıdan önce bütün noktalar bir kez iki ayrı ölçüte göre sıralanır. Satırlar şöyle çalışır:

• if (n <= 3) return kabaKuvvet(X); taban durumdur. Üç ya da daha az nokta için kaba kuvvet en çok üç uzaklık hesaplar; bölmeye değmez. Eşiğin 3 olmasının bir nedeni daha vardır: tek noktalı bir yarıda en yakın çift tanımsızdır.
• Nokta m = X.get(orta); bölme doğrusunu belirler: L, x = m.x doğrusudur. Sol yarı X.subList(0, orta), sağ yarı X.subList(orta, n)'dir.
• Ysol ve Ysag, Y'nin iki yarıya düşen noktalarıdır ve y sırasını korur. Kod bunların kurulmasını bir açıklama satırıyla geçer; bir yolu aşağıda verilmiştir.
• İki özyinelemeli çağrı dSol ve dSag'ı verir; d bunların küçüğüdür.
• İlk for döngüsü şeridi kurar. Y üzerinde gezildiği için şerit kendiliğinden y'ye göre sıralıdır; ayrıca sıralamaya gerek yoktur.
• İç içe döngüler şeridi tarar. İç döngünün koşulu s.get(j).y - p.y < d'dir; d küçüldükçe döngü daha erken durur. Daha yakın bir çift bulunursa d güncellenir.

List<Nokta> Ysol = new ArrayList<>(), Ysag = new ArrayList<>();
Set<Nokta> solYari = new HashSet<>(X.subList(0, orta));
for (Nokta p : Y)                  // y sırası korunur
  if (solYari.contains(p)) Ysol.add(p);
  else Ysag.add(p);

Bu parça Ysol ve Ysag'ı tek geçişte kurar. Sol yarının noktaları bir HashSet'e konur; Y sırayla gezilir ve her nokta, sol yarıda olup olmamasına göre iki listeden birine eklenir. Nokta sınıfı equals metodunu yeniden tanımlamadığı için küme nesnelerin kimliğiyle çalışır; aynı koordinatlı iki farklı nokta bile karışmaz. Geçiş beklenen O(n) sürer ve listeler y sırasını korur. Yeniden sıralama yapılmaz.

6.5.5Kod izleme: 10 nokta

İzlemede on nokta kullanılır: (2,3), (12,30), (40,50), (5,1), (12,10), (3,4), (7,7), (17,17), (27,27), (28,27). x'e göre sıralı liste X = [(2,3), (3,4), (5,1), (7,7), (12,30), (12,10), (17,17), (27,27), (28,27), (40,50)]'dir. Aynı x'e sahip (12,30) ve (12,10) noktaları, sıralama kararlı olduğu için girdideki sıralarını korur. y'ye göre sıralı liste Y = [(5,1), (2,3), (3,4), (7,7), (12,10), (17,17), (27,27), (28,27), (12,30), (40,50)]'dir.

Sonuç d = 1,00'dır; en yakın çift (27,27)–(28,27)'dir. Bu çift sağ yarının sağ yarısında, tabandaki kaba kuvvetle bulunmuştur. Bu örnekte şeritler hiçbir çift karşılaştırması yapmaz. Bunun nedeni, δ'nın erkenden küçük çıkması ve şeritlerin çok daralmasıdır. Algoritmanın toplam işi 8 uzaklık hesabıdır (3. adımda 1, 4. adımda 3, 8. adımda 1, 9. adımda 3). Kaba kuvvet aynı girdide 45 uzaklık hesaplardı.

Şeridin gerçekten iş yaptığı bir örnek de görülmelidir. L doğrusu x = 10'da olsun ve iki yarıdan δ_L = 5, δ_R = 4 dönsün. Y listesi (8,1), (13,2), (11,4), (7,6), (12,9), (9,10), (15,12) olsun.

6.5.6Analiz

Özyinelemenin her düzeyinde bölme, şerit kurma ve şerit tarama birlikte O(n) sürer. Bağıntı birleştirme sıralamasınınkiyle aynıdır: T(n) = 2T(n/2) + O(n) ve sonuç O(n log n). Başlangıçtaki iki sıralama da O(n log n) sürdüğü için toplam süre O(n log n)'dir. Bu süre en iyisidir. Cebirsel karar ağacı modelinde, noktaların hepsinin farklı olup olmadığını sınamak bile Ω(n log n) gerektirir. En yakın uzaklığın sıfır olup olmadığı da bu soruyu yanıtlar.

Taban durumun seçimi de algoritmayı etkiler. Eşik n ≤ 3 yerine n ≤ 1 olsaydı tek noktalı yarı Double.MAX_VALUE, yani pratikte sonsuz döndürürdü. Sonuç yine doğru olurdu. İki noktalı bir aralık iki tek noktaya bölünür ve d sonsuz kalır. Şerit iki noktayı da içerir ve şerit taraması kaçan çifti bulur. Ama çağrı sayısı artar ve küçük girdilerde gereksiz özyineleme yükü oluşur.

6.6Karatsuba çarpımı

İki tam sayıyı çarpmak, bilgisayarın tek komutla yaptığı bir iş gibi görünür. Bu yalnız sayılar bir makine sözcüğüne, örneğin 64 bite sığdığı sürece doğrudur. Şifrelemede, bilimsel hesapta ve bilgisayar cebirinde yüzlerce ya da binlerce basamaklı sayılar çarpılır. Bu sayılar basamak dizileri olarak tutulur ve çarpmanın süresi basamak sayısına bağlıdır. 1960'ta Kolmogorov, iki n basamaklı sayının çarpımının Ω(n²) işlem gerektirdiğini öne sürdü. Henüz öğrenci olan Anatoli Karatsuba kısa sürede bu savın yanlış olduğunu gösteren algoritmayı buldu.

6.6.1Okul yöntemi ve saf bölme

İlkokulda öğrenilen çarpma yönteminde ikinci sayının her basamağı birinci sayının her basamağıyla çarpılır ve kaydırılmış ara sonuçlar toplanır. İki n basamaklı sayı için n² tek basamaklı çarpım yapılır: süre O(n²)'dir.

Böl ve fethetin ilk denemesi sayıları ikiye bölmektir. n basamaklı x ve y, m = ⌊n/2⌋ noktasından bölünür:

x = a · 10^m + b,   y = c · 10^m + d

Burada a ve c sayıların üst yarıları, b ve d alt yarılarıdır. Örneğin 1234 = 12 · 100 + 34'tür. Çarpım açılınca

x · y = ac · 10^2m + (ad + bc) · 10^m + bd

bulunur. 10^m ile çarpmak yalnız sola m sıfır eklemektir ve O(n) sürer; toplamalar da O(n) sürer. Asıl iş dört yarım boyutlu çarpımdır: ac, ad, bc, bd. Bağıntı T(n) = 4T(n/2) + O(n) olur. Ana teoremde n^{log₂ 4} = n² baskındır ve sonuç O(n²)'dir. Saf bölme hiçbir kazanç sağlamaz: dört çarpımın her biri n²/4 sürer ve toplam yine n²'dir.

6.6.2Dört çarpım yerine üç

Karatsuba'nın gözlemi, ortadaki ad + bc teriminin iki ayrı çarpım gerektirmediğidir. Şu eşitlik vardır:

(a + b)(c + d) = ac + (ad + bc) + bd   ⇒   ad + bc = (a + b)(c + d) − ac − bd

ac ve bd zaten hesaplanacaktır. Bir çarpım daha, (a + b)(c + d), yapılınca orta terim iki çıkarmayla elde edilir. Üç çarpım şöyle adlandırılır:

z₂ = ac,   z₀ = bd,   z₁ = (a + b)(c + d),   x · y = z₂ · 10^2m + (z₁ − z₂ − z₀) · 10^m + z₀

Bir çarpımdan kurtulmanın bedeli birkaç fazladan toplama ve çıkarmadır. Toplamalar O(n) sürer; çarpımlar ise yarım boyutlu birer problemdir ve özyinelemeyle çözülür. Bağıntı T(n) = 3T(n/2) + O(n) olur.

6.6.3Kod: karatsuba()

long karatsuba(long x, long y) {
  if (x < 10 || y < 10) return x * y; // taban
  int n = Math.max(basamak(x), basamak(y));
  long p = (long) Math.pow(10, n / 2);
  long a = x / p, b = x % p;   // x = a·p + b
  long c = y / p, d = y % p;   // y = c·p + d
  long z0 = karatsuba(b, d);
  long z1 = karatsuba(a + b, c + d);
  long z2 = karatsuba(a, c);
  return z2 * p * p + (z1 - z2 - z0) * p + z0;
}

Kod formülün doğrudan karşılığıdır:

• if (x < 10 || y < 10) return x * y; taban durumdur. Çarpanlardan biri tek basamaklıysa çarpım doğrudan yapılır. Koşulun “ya da” ile kurulması önemlidir: 7 · 15 gibi bir çarpımda bölme anlamsızdır, çünkü 7'nin üst yarısı yoktur.
• n iki sayının basamak sayılarının büyüğüdür; p = 10n/2 bölme noktasıdır. Math.pow bir double döndürür; 10'un küçük kuvvetleri double'da tam gösterildiği için (long) dönüşümü güvenlidir.
• a = x / p ve b = x % p üst ve alt yarıdır; c ve d de y için aynıdır.
• Üç özyinelemeli çağrı sırasıyla z0, z1, z2'yi hesaplar. Son satır sonuçları birleştirir.

Basamak sayısını veren yardımcı metot basittir:

int basamak(long x) {
  return String.valueOf(Math.abs(x)).length();
}

Bu Java kodu algoritmayı göstermek içindir. long türü en çok 19 basamaklı sayıları tuttuğu için büyük sayılarda kullanılamaz. Gerçek uygulamalar sayıları basamak dizileri olarak tutar; Java'da bu iş BigInteger sınıfıyla yapılır. Kodun doğruluğu yine de denetlenebilir: rastgele seçilen 100 000 sayı çiftinde karatsuba(x, y) ile x * y aynı sonucu vermiştir.

6.6.4Kod izleme: 1234 · 5678

karatsuba(1234, 5678) çağrısında n = 4, p = 100'dür. Çağrı, (34, 78), (46, 134) ve (12, 56) için üç alt çağrı yapar. Tablo 6.12 bütün çağrıları çağrılma sırasıyla verir.

İzlemenin ilginç noktası (46, 134) çağrısıdır. z₁ için yarıların toplamı alındığında sayılar bir basamak büyüyebilir: 12 + 34 = 46 iki basamaklıdır, ama 56 + 78 = 134 üç basamaklıdır. Kod bunu kendiliğinden karşılar: n iki sayının basamak sayısının büyüğüdür ve p = 10^⌊3/2⌋ = 10 seçilir. Bölme 46 = 4 · 10 + 6 ve 134 = 13 · 10 + 4 olur. Bu bir basamaklık büyüme süre mertebesini değiştirmez.

Toplam 16 çağrı yapılır: 1 kök, 3 çocuk, 9 torun ve (10, 17)'nin 3 çocuğu. 11 çağrı taban durumdur. Okul yöntemi aynı çarpım için 16 tek basamaklı çarpım yapar. Bu küçük örnekte kazanç belirgin değildir, çünkü taban çarpımlarından bazıları (7 · 15, 4 · 13, 3 · 11) tek basamaklı çarpımdan büyüktür. Kazanç büyük sayılarda ortaya çıkar.

6.6.5Analiz ve pratik

Bağıntı T(n) = 3T(n/2) + O(n)'dir. n^{log₂ 3} ≈ n^1,585, f(n) = n'den polinom olarak büyüktür. Ana teoremin 1. durumundan T(n) = Θ(n^{log₂ 3}) ≈ Θ(n^1,585) çıkar. Aynı sonuç sayarak da bulunur. n = 2^k basamaklı sayılarda her düzeyde çarpım sayısı 3 katına çıkar ve k düzey sonra tek basamaklı çarpımlara inilir. Tek basamaklı çarpım sayısı 3^k = 3^{log₂ n} = n^{log₂ 3}'tür. Örneğin n = 8 için 3³ = 27 çarpım yapılır; okul yöntemi 64 çarpım yapar.

Oran n^0,415 gibi büyür: bin basamakta yaklaşık 18, bir milyon basamakta yaklaşık 300 kat. Ancak tablo sabit çarpanları göstermez. Karatsuba her düzeyde fazladan toplama, çıkarma ve geçici sayılar kullanır. Küçük sayılarda bu yük kazancı aşar ve Karatsuba okul yönteminden yavaştır. Bu yüzden uygulamalar bir eşik kullanır: sayı belirli bir basamak sayısının altına inince okul yöntemine geçilir.

Java'nın BigInteger.multiply metodu bu yaklaşımı izler: küçük sayılarda okul yöntemini, büyük sayılarda Karatsuba'yı, daha büyüklerinde Toom-Cook yöntemini kullanır. Toom-Cook, Karatsuba fikrinin genellemesidir: sayıyı üç parçaya bölüp dokuz yerine beş çarpım yapar ve O(n^{log₃ 5}) ≈ O(n^1,465) süre verir. Daha da hızlı algoritmalar hızlı Fourier dönüşümüne dayanır. Schönhage–Strassen algoritması O(n log n log log n) sürer. Harvey ve van der Hoeven'in 2019'da duyurduğu algoritma O(n log n) sürer. Bu son algoritma kuramsal öneme sahiptir; sabitleri çok büyük olduğu için pratikte kullanılmaz.

6.7Strassen matris çarpımı

Karatsuba'nın fikri matrislere de uygulanır. 1969'da Volker Strassen, iki matrisin çarpımının klasik Θ(n³) yöntemden hızlı yapılabileceğini gösterdi. Yöntem yine bir özyinelemeli çağrıyı eksiltmeye dayanır: sekiz blok çarpımı yerine yedi.

6.7.1Klasik ve blok matris çarpımı

n × n boyutlu A ve B matrislerinin çarpımı C = A · B'nin her hücresi, A'nın bir satırıyla B'nin bir sütununun iç çarpımıdır: C[i][j] = Σ_k A[i][k] · B[k][j]. Klasik yöntem bu tanımı üç iç içe döngüyle yazar:

for (int i = 0; i < n; i++)
  for (int j = 0; j < n; j++)
    for (int k = 0; k < n; k++)
      C[i][j] += A[i][k] * B[k][j];

n² hücrenin her biri için n çarpım yapılır: toplam n³ çarpım. Kodda C'nin başlangıçta sıfırlarla dolu olduğu varsayılır; Java'da yeni oluşturulan dizi zaten sıfırlarla doludur.

Böl ve fethetin ilk denemesi, her matrisi n/2 × n/2'lik dört bloğa bölmektir:

A = [A₁₁ A₁₂; A₂₁ A₂₂],   B = [B₁₁ B₁₂; B₂₁ B₂₂],   C = [C₁₁ C₁₂; C₂₁ C₂₂]

Bloklar sayı gibi çarpılıp toplanabilir; yalnız çarpımın sırası değiştirilemez. Sonuç blokları şöyledir:

• C₁₁ = A₁₁ · B₁₁ + A₁₂ · B₂₁
• C₁₂ = A₁₁ · B₁₂ + A₁₂ · B₂₂
• C₂₁ = A₂₁ · B₁₁ + A₂₂ · B₂₁
• C₂₂ = A₂₁ · B₁₂ + A₂₂ · B₂₂

Sekiz blok çarpımı ve dört blok toplamı gerekir. Bir blok toplamı (n/2)² hücreyi toplar ve Θ(n²) sürer. Bağıntı T(n) = 8T(n/2) + Θ(n²) olur; n^{log₂ 8} = n³ baskındır ve sonuç Θ(n³)'tür. Karatsuba'daki saf bölmede olduğu gibi yalnız bölmek yetmez; çarpım sayısı azaltılmalıdır.

6.7.2Sekiz yerine yedi çarpım

Strassen, yedi ara çarpımın uygun toplamlarıyla dört sonuç bloğunun da elde edilebileceğini gösterdi. Tablo 6.14 bu çarpımları ve sonuç bloklarını verir.

Formüllerin doğruluğu açılarak denetlenir. C₁₂ en kolay olanıdır: P₁ + P₂ = A₁₁B₁₂ − A₁₁B₂₂ + A₁₁B₂₂ + A₁₂B₂₂ = A₁₁B₁₂ + A₁₂B₂₂. C₁₁ için P₅, P₄, P₂ ve P₆ açılınca on iki terim yazılır. Bunlardan sekizi birbirini götürür ve geriye A₁₁B₁₁ + A₁₂B₂₁ kalır. Burada çarpımların sırası korunmalıdır: matrislerde A₁₁B₁₁ ile B₁₁A₁₁ genellikle farklıdır. Strassen'in formülleri hiçbir yerde çarpımın değişme özelliğini kullanmaz; bu yüzden bloklar için de geçerlidir.

Yedi çarpımın yanında 18 blok toplama ya da çıkarma yapılır: P'lerin tanımında 10, sonuç bloklarında 8. Bloklar da Strassen ile özyinelemeli çarpılır; taban durum 1 × 1 matristir, yani tek bir sayı çarpımıdır.

6.7.3Adım adım: 2 × 2 örnek

6.7.4Analiz ve pratik

Bağıntı T(n) = 7T(n/2) + Θ(n²)'dir. n^{log₂ 7} ≈ n^2,807, n²'den polinom olarak büyüktür ve ana teoremin 1. durumundan T(n) = Θ(n^{log₂ 7}) ≈ Θ(n^2,807) çıkar. Sayarak da görülür: n = 2^k için skaler çarpım sayısı 7^k'dir; klasik yöntem 8^k = n³ çarpım yapar. 16 × 16 matrislerde Strassen 2401, klasik yöntem 4096 çarpım yapar. n = 1024 = 2¹⁰ için 7¹⁰ ≈ 2,8 · 10⁸ ve 8¹⁰ ≈ 1,07 · 10⁹'dur; Strassen yaklaşık 3,8 kat daha az çarpım yapar.

Algoritmanın pratikte bazı sorunları vardır:

• Boyut. n 2'nin kuvveti değilse matris sıfırlarla doldurularak en yakın kuvvete büyütülür (padding). Sıfırlar sonucu değiştirmez, ama işi artırır.
• Eşik. 18 ek toplama ve geçici matrisler yüzünden küçük n'de Strassen klasik yöntemden yavaştır. Kütüphaneler alt matris boyu 64–128 civarına inince klasik yönteme geçer.
• Sayısal kararlılık. Kayan noktalı sayılarda çıkarma işlemleri yuvarlama hatasını büyütebilir. Klasik yöntem bu açıdan daha güvenilirdir.
• Bellek. Her düzeyde geçici bloklar oluşturulur; ek bellek O(n²)'dir.

Strassen'den sonra matris çarpımının üssü ω için daha küçük üst sınırlar bulundu. 2024 itibarıyla bilinen sınır ω < 2,372'dir. Bu algoritmaların sabitleri o kadar büyüktür ki pratikte kullanılmazlar. Strassen'in asıl dersi kuramsaldır: çarpımı toplamalarla takas etmek, a'yı bir azaltarak üssü düşürür. Aynı fikir Karatsuba'da 4'ten 3'e, Strassen'de 8'den 7'ye inişte görülür.

6.8Değerlendirme

Tablo 6.15 bu notta ele alınan problemlerde saf yöntem ile böl ve fethet çözümünü yan yana koyar.

Kazancın kaynağı üç türlüdür. Birincisi, iş dengeli bölünür ve her düzey O(n)'de birleştirilir: sıralama ve en yakın nokta çifti. İkincisi, alt problem sayısı azaltılır: Karatsuba ve Strassen. Üçüncüsü, alt problemlerden biri tamamen atılır ya da tek bir alt problemin sonucu yeniden kullanılır: ikili arama ve hızlı üs alma. Quickhull ise ikinci ve üçüncü türün bir karışımıdır: üçgenin içindeki noktalar atılır ve kalan iş iki dengesiz parçaya bölünür.

Bir problemi böl ve fethetle çözmeye karar verirken sorulacak sorular şunlardır: Problem aynı türden küçük parçalara bölünebiliyor mu? Parçalar birbirinden bağımsız mı? Parçaların çözümleri, saf yöntemden daha ucuza birleştirilebiliyor mu? İlk iki sorunun yanıtı evet, üçüncüsünün yanıtı hayırsa böl ve fethet doğru ama yavaş bir algoritma verir; en büyük öğe örneğinde olduğu gibi. Parçalar örtüşüyorsa dinamik programlama, her adımda yerel en iyi seçim yetiyorsa açgözlü yaklaşım daha uygundur.

6.9Sık yapılan hatalar

• Taban durumu unutmak ya da hiç ulaşılamayan bir taban durum yazmak. Sonuç sonsuz özyineleme ve StackOverflowError'dır. Karatsuba'da taban durum x < 10 || y < 10'dur. Bu satır silinirse tek basamaklı sayılarda p = 10⁰ = 1 olur. karatsuba(4, 8) ilk alt çağrıda karatsuba(0, 0)'ı çağırır; o da kendini aynı argümanlarla yeniden çağırır ve özyineleme hiç bitmez.
• Dengesiz bölme. Sıralı dizide son öğenin pivot seçilmesi ya da Quickhull'da her adımda yalnız bir noktanın ayrılması T(n) = T(n − 1) + n = O(n²) verir.
• Örtüşen alt problemleri fark etmemek. Fibonacci'yi düz özyinelemeyle hesaplamak üstel süre alır; sonuçları saklayan dinamik programlama gerekir.
• Aynı alt problemi iki kez çağırmak. Hızlı üs almada us(x, n / 2)'yi iki kez çağırmak Θ(log n)'yi Θ(n)'ye çıkarır.
• Birleştirme maliyetini küçümsemek. En yakın nokta çiftinde şeridi her çağrıda sıralamak süreyi O(n log² n) yapar; 2T(n/2) + n log n ≠ Θ(n log n).
• Ana teoremi yanlış yerde kullanmak. T(n) = T(n − 1) + n, eşit olmayan bölmeler ve f(n) = n/log n gibi durumlar arasında kalan fonksiyonlar teoremin kapsamı dışındadır.
• İşaret ve yön hataları. Strassen'de C₂₂ = P₅ + P₁ − P₃ − P₇'deki tek bir işaret hatası hata vermeden yanlış matris üretir. Quickhull'da capraz'a verilen nokta sırası karışırsa üst ve alt küme yer değiştirir. Küçük bir örnekte saf yöntemle karşılaştırma bu hataları yakalar.
• Böl ve fethetin her zaman hızlandırdığını sanmak. En büyük öğe probleminde böl ve fethet de n − 1 karşılaştırma yapar; kazanç süre değil, paralelliktir.

6.10Özet

• Böl ve fethet, problemi aynı türden, küçük ve bağımsız alt problemlere böler, alt problemleri özyinelemeyle çözer ve sonuçları birleştirir. Taban durum şarttır.
• Süre T(n) = aT(n/b) + f(n) bağıntısıyla ifade edilir. Ana teorem f(n)'yi n^{log_b a} ile karşılaştırır: yapraklar baskınsa Θ(n^{log_b a}), eşitse bir log n çarpanı eklenir, kök baskınsa Θ(f(n)).
• Eşit olmayan ya da sabit miktarda küçülen bölmelerde ana teorem uygulanmaz; özyineleme ağacı kullanılır.
• Birleştirme sıralamasında asıl iş birleştirmede, hızlı sıralamada parçalamadadır. İkili arama ve hızlı üs alma tek alt problemle O(log n) sürer.
• Alt problemler örtüşüyorsa (Fibonacci) böl ve fethet üstel süre alır; dinamik programlama gerekir.
• Quickhull en sol ve en sağ noktadan başlar, her adımda doğruya en uzak noktayı (en büyük capraz) örtüye ekler ve üçgenin içini eler. Ortalama O(n log n), en kötü O(n²), çıktıya duyarlı O(n · h) sürer.
• En yakın nokta çiftinde noktalar x'e göre ikiye bölünür, δ = min(δ_L, δ_R) alınır ve 2δ genişliğindeki şerit y sırasıyla taranır. Her nokta en çok 7 komşuyla karşılaştırılır; süre O(n log n)'dir.
• Karatsuba ad + bc = (a + b)(c + d) − ac − bd eşitliğiyle dört çarpım yerine üç yapar: Θ(n^1,585).
• Strassen sekiz blok çarpımı yerine yedi yapar: Θ(n^2,807). Her iki algoritmada kazanç, a'yı bir azaltmaktan gelir; küçük girdilerde bir eşiğin altında saf yönteme geçilir.

6.11Kavram listesi

• böl ve fethet divide and conquer
• taban durum base case
• alt problem subproblem
• özyineleme recursion
• özyineleme bağıntısı recurrence (relation)
• özyineleme ağacı recursion tree
• ana teorem master theorem
• birleştirme sıralaması merge sort
• hızlı sıralama quick sort
• parçalama partition
• ikili arama binary search
• örtüşen alt problemler overlapping subproblems
• dinamik programlama dynamic programming
• dışbükey örtü convex hull
• en yakın nokta çifti closest pair of points
• kaba kuvvet brute force
• alt sınır lower bound
• Karatsuba çarpımı Karatsuba multiplication
• Strassen algoritması Strassen's algorithm

6.12Kendini Dene

1. Şu bağıntıların ana teoreme göre çözümü nedir? (a) T(n) = 3T(n/3) + n, (b) T(n) = T(n/2) + n, (c) T(n) = 16T(n/4) + n².

   Cevap

   (a) n^{log₃ 3} = n = f(n); durum 2: Θ(n log n). (b) n^{log₂ 1} = 1, f(n) = n polinom olarak büyük; düzenlilik f(n/2) = n/2 ≤ ½ · n sağlanır; durum 3: Θ(n). (c) n^{log₄ 16} = n² = f(n); durum 2: Θ(n² log n).

2. enBuyuk metodu [3, 8, 1, 9, 4, 6] dizisinde enBuyuk(a, 0, 5) ile çağrılıyor. Toplam kaç çağrı ve kaç karşılaştırma yapılır, sonuç nedir?

   Cevap

   Altı öğe için özyineleme ağacında 6 yaprak ve 5 iç düğüm vardır: 11 çağrı, 5 karşılaştırma. İlk bölme [0..2] ve [3..5]'tir; sol yarının en büyüğü 8, sağ yarınınki 9'dur. Sonuç 9'dur.

3. us(2, 25) kaç özyinelemeli çağrı ve kaç çarpım yapar? Saf yöntem kaç çarpım yapar?

   Cevap

   Üs dizisi 25 → 12 → 6 → 3 → 1 → 0'dır: 6 çağrı. Çarpımlar: n = 1 (tek) 2, n = 3 (tek) 2, n = 6 (çift) 1, n = 12 (çift) 1, n = 25 (tek) 2; toplam 8. Sonuç 2²⁵ = 33 554 432'dir. Saf yöntem 24 çarpım yapar.

4. A = (0, 0), B = (10, 0) ve üst kümede (2,3), (5,6), (8,2), (5,2) noktaları olsun. Quickhull hangi noktayı C seçer? Hangi noktalar elenir, hangisiyle özyineleme sürer?

   Cevap

   capraz(A, B, P) = 10 · P_y: değerler 30, 60, 20, 20'dir; C = (5, 6). capraz(A, C, (2,3)) = 5 · 3 − 6 · 2 = 3 > 0: (2,3), AC'nin dışındadır. (8,2) için capraz(C, B, ·) = 5 · (−4) − (−6) · 3 = −2, (5,2) için capraz(A, C, ·) = −20 ve capraz(C, B, ·) = −20'dir: ikisi de üçgenin içindedir ve elenir. Özyineleme AC tarafında yalnız (2,3) ile sürer; CB tarafı boştur.

5. En yakın çift algoritmasında L doğrusu x = 10'dadır ve iki yarıdan δ = 3 dönmüştür. Y listesi (9,1), (11,2), (14,4), (10,5), (8,6), (12,7)'dir. Şerit hangi noktalardan oluşur, kaç uzaklık hesaplanır ve sonuç ne olur?

   Cevap

   (14,4) için |14 − 10| = 4 ≥ 3; şerit dışındadır. Şerit: (9,1), (11,2), (10,5), (8,6), (12,7). (9,1)–(11,2) uzaklığı √5 ≈ 2,24'tür ve d 2,24 olur; (10,5)'in y farkı 4 olduğu için iç döngü durur. (11,2)'den sonra (10,5)'in y farkı 3; durur. (10,5)–(8,6) = 2,24 ve (10,5)–(12,7) ≈ 2,83 hesaplanır. (8,6)–(12,7) ≈ 4,12 hesaplanır. Toplam 4 uzaklık; sonuç d = √5 ≈ 2,24.

6. karatsuba(56, 78) çağrısında hangi alt çağrılar yapılır? Kaç çağrı yapılır, kaçı taban durumdur?

   Cevap

   p = 10; a = 5, b = 6, c = 7, d = 8. z₀ = 6 · 8 = 48 (taban). z₁ = karatsuba(11, 15): iç bölmede 1, 1, 1, 5; iç çarpımlar 1 · 5 = 5, 2 · 6 = 12, 1 · 1 = 1; sonuç 100 + (12 − 1 − 5) · 10 + 5 = 165. z₂ = 5 · 7 = 35 (taban). Sonuç 35 · 100 + (165 − 35 − 48) · 10 + 48 = 4368. Toplam 7 çağrı, 5'i taban durum.

7. A = [[1, 0], [2, 1]] ve B = [[3, 1], [0, 2]] matrislerinin Strassen ile çarpımında P₁, …, P₇ ve C nedir?

   Cevap

   P₁ = 1 · (1 − 2) = −1, P₂ = (1 + 0) · 2 = 2, P₃ = (2 + 1) · 3 = 9, P₄ = 1 · (0 − 3) = −3, P₅ = (1 + 1)(3 + 2) = 10, P₆ = (0 − 1)(0 + 2) = −2, P₇ = (1 − 2)(3 + 1) = −4. C₁₁ = 10 − 3 − 2 − 2 = 3, C₁₂ = −1 + 2 = 1, C₂₁ = 9 − 3 = 6, C₂₂ = 10 − 1 − 9 + 4 = 4. C = [[3, 1], [6, 4]]; klasik yöntem de aynı sonucu verir.

8. Karatsuba fikri genelleştirilip sayılar üç parçaya bölünüyor ve dokuz parça çarpımı yerine beş çarpım yapılıyor. Bölme ve birleştirme O(n) sürüyorsa algoritmanın süresi nedir? Karatsuba'dan hızlı mıdır?

   Cevap

   T(n) = 5T(n/3) + O(n). n^{log₃ 5} ≈ n^1,465 baskındır; durum 1: Θ(n^1,465). Karatsuba'nın n^1,585'inden asimptotik olarak hızlıdır; sabitleri daha büyük olduğu için ancak daha büyük sayılarda öne geçer. Toom-Cook yöntemi budur.

9. Saf özyinelemeli fib(6) kaç çağrı yapar? Neden böl ve fethet burada uygun değildir?

   Cevap

   C(n) = 1 + C(n − 1) + C(n − 2), C(0) = C(1) = 1: C(5) = 15, C(4) = 9, C(6) = 25. Alt problemler bağımsız değildir: F(4) hesaplanırken F(3), F(2) … zaten hesaplanır ve ikinci daldan yeniden hesaplanır. Sonuçlar saklanırsa (dinamik programlama) her F(k) bir kez hesaplanır ve süre O(n) olur.

6.13İleri okuma

• T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms (4. baskı, 2022), Bölüm 4: Strassen algoritmasını, özyineleme ağacı ve yerine koyma yöntemlerini ve ana teoremin ispatını verir. Bölüm 33 dışbükey örtü ve en yakın nokta çiftini işler.
• J. Kleinberg, É. Tardos, Algorithm Design (2005), Bölüm 5: böl ve fethet bağıntılarını sezgisel olarak açar; en yakın nokta çifti ve tam sayı çarpımı için okunaklı anlatımlar içerir.
• C. B. Barber, D. P. Dobkin, H. Huhdanpaa, “The Quickhull Algorithm for Convex Hulls” (1996): Quickhull'u yüksek boyutlara genelleyen ve yaygın kullanılan Qhull yazılımının temelini oluşturan makale.
• V. Strassen, “Gaussian Elimination is not Optimal” (1969): yedi çarpım fikrini tanıtan ve yalnız birkaç sayfadan oluşan özgün makale.

6.14Kaynaklar

1. C. B. Barber, D. P. Dobkin, H. Huhdanpaa, “The Quickhull Algorithm for Convex Hulls”, ACM Transactions on Mathematical Software 22(4), 1996.
2. T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to Algorithms, 4. baskı, MIT Press, 2022 (Bölüm 4: Divide-and-Conquer; Bölüm 33: Computational Geometry).
3. A. Karatsuba, Yu. Ofman, “Multiplication of Multidigit Numbers on Automata”, 1962.
4. J. Kleinberg, É. Tardos, Algorithm Design, Pearson, 2005 (Bölüm 5: Divide and Conquer).
5. R. Sedgewick, K. Wayne, Algorithms, 4. baskı, Addison-Wesley, 2011.
6. V. Strassen, “Gaussian Elimination is not Optimal”, Numerische Mathematik 13, 1969.

İlgili sayfalar: Bölüm 6 sunumu · Çalışma soruları · Terim sözlüğü · © Sercan Külcü. Tüm hakları saklıdır.