Što je paradigma podijeli pa vladaj?

Question

Accepted Answer

**Podijeli pa vladaj** rješava problem (1) **podjelom** na manje podprobleme, (2) **osvajanjem** svakog rekurzivno, i (3) **kombiniranjem** rezultata. Mnogi učinkoviti algoritmi slijede ovaj predložak.

## Ideja

Ako su podproblemi nezavisni i brzo se smanjuju, ukupan rad slijedi ponavljanje koje možete analizirati s **Master Theorem**.

## Primjer: maksimalni element putem podijeli pa vladaj

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

## Klasični primjeri

- **Merge sort / quicksort** — O(n log n) sortiranje.
- **Binarno pretraživanje** — O(log n).
- **Brzo potenciranje, Karatsuba množenje, najbliži par.**

## Složenost

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

## Kada koristiti / zamke

Koristite kada se problem **čisto dijeli** na nezavisne podprobleme. Ako se podproblemi **preklanjaju**, radije odaberite dinamičko programiranje (kako biste izbjegli ponovno računanje). Režijski troškovi rekurzije i korak kombiniranja mogu biti dominantni za male ulaze.

## Zašto je to važno

Podijeli pa vladaj je ponovno iskoristivi plan iza velike frakcije učinkovitih algoritama.

Prepoznavanje uzorka omogućava vam da brzo izvedete i analizirate nove algoritme s ponavljanjem.

Također se prirodno preslikava na paralelizam, jer nezavisni podproblemi mogu raditi istovremeno.