Böl ve Yönet

İngilizcesi: Divide and Conquer
Türkçe karşılığı: böl ve fethet
Okunuşu: divayd end konkır

Güncellendi 30 Eylül 20262 dk okuma

Kısaca

Böl ve yönet, bir problemi daha küçük bağımsız parçalara bölen, her birini özyinelemeyle çözen ve sonuçları birleştiren bir algoritma tasarım tekniğidir.

Böl ve yönet (divide and conquer) nedir?

Böl ve yönet, algoritma tasarlamak için üç adımlı bir stratejidir. Önce problemi aynı türden daha küçük alt problemlere bölün; ikinci olarak her alt problemi, parçalar doğrudan çözülebilecek kadar küçülene dek özyinelemeyle çözerek yönetin; üçüncü olarak kısmi cevapları tüm problemin cevabında birleştirin. Küçük ve doğrudan çözülebilen duruma temel durum (base case) denir.

Bir böl ve yönet algoritmasının çalışma süresi, kaç alt problem oluşturduğuna, bunların ne kadar büyük olduğuna ve bölme ile birleştirmenin ne kadar iş gerektirdiğine bağlıdır. Merge sort bir listeyi iki yarıya böler, her birini sıralar ve doğrusal sürede birleştirir; bunların toplamı O(n log n) eder. İkili arama ise aralığı bölen ama yalnızca bir yarıda devam etmesi gereken daha basit bir durumdur. Bu tür maliyetler, merge sort için T(n) = 2T(n/2) + O(n) gibi özyineleme bağıntıları olarak yazılır ve master teoremi denen standart bir sonuç bunların birçoğunu çözer. Alt problemler bağımsız olduğu için çoğu zaman farklı CPU çekirdeklerinde ya da makinelerde paralel olarak çözülebilir.

Bir öğretmenin bin sınav kâğıdını notlandırması gibidir: yığını on yardımcıya bölüştürün, gerekirse her biri kendi payını daha da bölsün, sonra bitmiş yığınları toplayın. Klasik böl ve yönet algoritmaları arasında merge sort, quicksort, ikili arama, büyük sayıların Karatsuba hızlı çarpımı, ses ve sinyal işlemede kullanılan hızlı Fourier dönüşümü (FFT) ve en yakın nokta çiftini bulma bulunur. Aynı fikir, devasa bir işin birçok makineye bölündüğü ve kısmi sonuçların birleştirildiği dağıtık veri işlemede daha büyük ölçekte görülür.

Böl ve yönet, problemleri alt problemlere ayıran dinamik programlamayla sıklıkla karıştırılır. Fark çakışmadır: böl ve yönette alt problemler bağımsızdır, bu yüzden her biri zaten bir kez çözülür; dinamik programlamada ise aynı alt problemler çok kez tekrar eder, bu yüzden sonuçları saklanır ve yeniden kullanılır. Özyinelemeyle de ilişkilidir ama ondan daha geniştir: özyineleme bir kodlama tekniğidir, böl ve yönet ise genellikle özyinelemeli yazılan bir çözüm yapılandırma biçimidir.

Önemli noktalar

Böl ve yönet, bir problemi bağımsız alt problemlere böler, her birini özyinelemeyle çözer ve cevapları birleştirir.
Merge sort, quicksort, ikili arama ve hızlı Fourier dönüşümü klasik örneklerdir.
Çalışma süreleri T(n) = 2T(n/2) + O(n) gibi özyineleme bağıntılarıyla ifade edilir ve bu O(n log n) verir.
Bağımsız alt problemler birçok böl ve yönet algoritmasını kolayca paralelleştirilebilir kılar.
Alt problemler çakıştığında ve tekrar ettiğinde bunun yerine dinamik programlama kullanılır.

Örnek

Problemi yarıya bölerek hızlı üs almapython

def power(base, exp):
    # Divide: x^n = (x^(n/2))^2, so each step halves the exponent
    if exp == 0:
        return 1                      # base case: solved directly
    half = power(base, exp // 2)      # conquer the smaller subproblem once
    result = half * half              # combine
    return result * base if exp % 2 else result

print(power(3, 13))                 # 1594323
print(power(2, 1000) == 2 ** 1000)  # True, after only about 10 levels of recursion

Sık sorulan sorular

Böl ve yönet ile dinamik programlama arasındaki fark nedir?

İkisi de bir problemi alt problemlere böler, ancak böl ve yönet alt problemler bağımsız olduğunda çalışır ve her biri bir kez çözülür. Dinamik programlama çakışan alt problemler içindir ve yeniden hesaplanmasınlar diye cevaplarını saklar.

İkili arama böl ve yönet midir?

Evet, basit bir biçimde: arama aralığını ikiye böler ve birleştirme adımı olmadan yalnızca bir yarıda devam eder. Bazı ders kitapları bu özel duruma decrease and conquer der.

Hangi sıralama algoritmaları böl ve yönet kullanır?

Klasik olanlar merge sort ve quicksort'tur. Merge sort asıl işini birleştirirken, sıralı yarıları birleştirerek yapar; quicksort ise bölerken, öğeleri bir pivot etrafında bölümleyerek yapar.

İlgili sayfalar

Bu sayfada bir hata ya da eksik mi gördünüz?Düzeltme önerin