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

Question

Accepted Answer

**Böl ve yönet**, bir problemi (1) daha küçük alt problemlere **bölerek**, (2) her birini özyinelemeli olarak **çözerek** ve (3) sonuçları **birleştirerek** çözer. Birçok verimli algoritma bu şablonu takip eder.

## Fikir

Alt problemler bağımsız ve hızlı shrink oluyorsa, toplam iş **Master Theorem** ile analiz edebileceğiniz bir yineleme ilişkisini izler.

## Örnek: böl ve yönet ile maksimum elemanı bulma

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: one element
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # conquer left
    right = max_dc(arr, mid + 1, hi)   # conquer right
    return max(left, right)            # combine

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## Klasik örnekler

- **Merge sort / quicksort** — O(n log n) sıralama.
- **Binary search** — O(log n).
- **Hızlı üs alma, Karatsuba çarpması, en yakın çift.**

## Karmaşıklık

Çoğunlukla T(n) = a·T(n/b) + f(n); merge sort için, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Ne zaman kullanılır / tuzaklar

Bir problem **temiz bir şekilde** bağımsız alt problemlere ayrılabiliyorsa kullanın. Alt problemler **çakışıyorsa**, bunun yerine dinamik programlamayı tercih edin (yeniden hesaplamayı önlemek için). Özyineleme overhead'i ve birleştirme adımı küçük girdiler için baskın olabilir.

## Neden önemli

Böl ve yönet, verimli algoritmaların çoğunun arkasında duran yeniden kullanılabilir bir şablondur.

Paterni tanımak, yineleme ilişkileriyle yeni algoritmaları hızlı bir şekilde türetmenize ve analiz etmenize olanak sağlar.

Ayrıca bağımsız alt problemler eşzamanlı olarak çalışabildiğinden, paralelliğe doğal bir şekilde eşlenir.