Mi az oszd meg és uralkodj paradigma?

Question

Accepted Answer

**Oszd meg és uralkodj** egy problémát úgy old meg, hogy (1) **részekre bontja** azt kisebb részproblémákra, (2) **meghódít** mindegyiket rekurzívan, és (3) **kombinál** az eredményeket. Sok hatékony algoritmus követi ezt a sablont.

## Az ötlet

Ha a részproblémák függetlenek és gyorsan csökkennek, akkor a teljes munka egy olyan rekurrenziát követ, amelyet a **Master Theorem** segítségével elemezhet.

## Példa: maximális elem oszd meg és uralkodj segítségével

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

## Klasszikus példák

- **Merge sort / quicksort** — O(n log n) rendezés.
- **Bináris keresés** — O(log n).
- **Gyors hatványozás, Karatsuba szorzás, legközelebbi pár.**

## Összetettség

Gyakran T(n) = a·T(n/b) + f(n); a merge sort esetén T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Mikor használja / csapdák

Használja, amikor egy probléma **tisztán felbomlik** független részproblémákra. Ha a részproblémák **átfedésben** vannak, inkább válassza a dinamikus programozást (az újraszámítás elkerülése érdekében). A rekurzió terhelése és a kombinálási lépés az apró bemenetek esetén dominánsak lehetnek.

## Miért számít

Az oszd meg és uralkodj egy felhasználható terv, amely a hatékony algoritmusok nagy részének mögött húzódik.

A minta felismerése lehetővé teszi új algoritmusok gyors levezetését és elemzését rekurrenziákkal.

Természetes módon térképez a párhuzamosságra is, mivel a független részproblémák egyidejűleg futhatnak.