Kaj je paradigma deli in vladaj?

Question

Accepted Answer

**Deli in vladaj** rešuje problem z (1) **deljenjem** na manjše podprobleme, (2) **reševanjem** vsakega rekurzivno in (3) **kombiniranjem** rezultatov. Številni učinkoviti algoritmi sledijo tej predlogi.

## Ideja

Če so podproblemi neodvisni in se hitro zmanjšujejo, je skupna količina dela odvisna od rekurzivne enačbe, ki jo lahko analizirate s **Master teoremom**.

## Primer: največji element prek deli in 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 primeri

- **Merge sort / quicksort** — O(n log n) sortiranje.
- **Binarni iskalni** — O(log n).
- **Hitro potenciranje, Karatsubino množenje, iskanje najbližjega para.**

## Kompleksnost

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

## Kdaj uporabiti / pasti

Uporabite, ko se problem **lepo deli** na neodvisne podprobleme. Če se podproblemi **prekrivajo**, raje uporabite dinamičko programiranje (da se izognete ponovljenim izračunom). Splošni stroški rekurzije in korak kombiniranja lahko dominirajo pri majhnih vhodih.

## Zakaj je to pomembno

Deli in vladaj je ponovno uporabljiva predloga za ogromen delež učinkovitih algoritmov.

Prepoznavanje vzorca vam omogoča hitro izvedbo in analizo novih algoritmov z rekurzivnimi enačbami.

Naravno se preslika tudi na paralelizem, saj se neodvisni podproblemi lahko izvajajo sočasno.