Co je paradigma „rozděl a panuj

Question

Accepted Answer

**Rozděl a panuj** řeší problém pomocí (1) **rozdělení** na menší podproblémy, (2) **řešení** každého rekurzivně a (3) **kombinování** výsledků. Mnoho efektivních algoritmů následuje tuto šablonu.

## Idea

Pokud jsou podproblémy nezávislé a rychle se zmenšují, celková práce následuje relaci, kterou můžete analyzovat pomocí **Master Theoremu**.

## Příklad: maximum prvku pomocí rozděl a panuj

```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
```

## Klasické příklady

- **Merge sort / quicksort** — O(n log n) řazení.
- **Binary search** — O(log n).
- **Rychlé umocňování, Karacubovo násobení, nejbližší pár.**

## Složitost

Často T(n) = a·T(n/b) + f(n); pro merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Kdy použít / úskalí

Využijte, když se problém **čistě dělí** na nezávislé podproblémy. Pokud se podproblémy **překrývají**, raději zvolte dynamické programování (aby se zabránilo opakovanému výpočtu). Režie rekurze a krok kombinování mohou dominovat pro malé vstupy.

## Proč na tom záleží

Rozděl a panuj je opakovaně použitelná šablona za obrovským podílem efektivních algoritmů.

Poznání tohoto vzoru vám umožní rychle odvodit a analyzovat nové algoritmy pomocí relací.

Mapuje se také přirozeně na paralelizmus, protože nezávislé podproblémy mohou běžet souběžně.