Co to jest paradygmat dziel i zwyciężaj?

Question

Accepted Answer

**Dziel i zwyciężaj** rozwiązuje problem przez (1) **podzielenie** go na mniejsze podproblemy, (2) **pokonanie** każdego rekurencyjnie i (3) **połączenie** wyników. Wiele efektywnych algorytmów podąża tym schematem.

## Pomysł

Jeśli podproblemy są niezależne i szybko się zmniejszają, całkowita praca podąża relacją rekurencyjną, którą możesz analizować za pomocą **Twierdzenia Mistrza**.

## Przykład: element maksymalny poprzez dziel i zwyciężaj

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

## Klasyczne przykłady

- **Merge sort / quicksort** — O(n log n) sortowanie.
- **Binary search** — O(log n).
- **Fast exponentiation, Karatsuba multiplication, closest pair.**

## Złożoność

Często T(n) = a·T(n/b) + f(n); dla merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Kiedy używać / pułapki

Używaj, gdy problem **czyszczący się dzieli** na niezależne podproblemy. Jeśli podproblemy **się nakładają**, preferuj programowanie dynamiczne zamiast tego (aby uniknąć ponownych obliczeń). Narzut rekursji i krok łączenia mogą dominować dla małych wejść.

## Dlaczego to ważne

Dziel i zwyciężaj to wielokrotnie używalny szablon stojący za dużą częścią efektywnych algorytmów.

Rozpoznanie wzorca pozwala szybko wyprowadzać i analizować nowe algorytmy za pomocą relacji rekurencyjnych.

Mapuje się również naturalnie na równoległość, ponieważ niezależne podproblemy mogą działać jednocześnie.