Kas yra „skaldyk ir valdyk" paradigma?

Question

Accepted Answer

**Skaldyk ir valdyk** sprendžia problemą (1) **skaldydama** ją į mažesnes dalis, (2) **valdomai sprendžiant** kiekvieną dalį rekursyviai ir (3) **sujungiant** rezultatus. Daugelis efektyvių algoritmų vadovaujasi šiuo šablonu.

## Idėja

Jei dalinės problemos yra nepriklausomos ir greitai mažėja, bendras darbas atitinka pasikartojimą, kurį galite analizuoti naudodami **Master teoremą**.

## Pavyzdys: maksimalus elementas naudojant skaldyk ir valdyk

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

## Klasikiniai pavyzdžiai

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

## Sudėtingumas

Dažnai T(n) = a·T(n/b) + f(n); merge sort atveju T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Kada naudoti / spąstai

Naudokite, kai problema **aiškiai daloma** į nepriklausomas dalis. Jei dalinės problemos **sutampa**, naudokite dinaminio programavimo strategiją (kad išvengtumėte perskaičiavimo). Rekursijos pridėtinis kaštas ir sujungimo žingsnis gali dominuoti mažiems įvestims.

## Kodėl tai svarbu

Skaldyk ir valdyk yra pakartojamasis šablonas, esantis didelės efektyvių algoritmų dalies pagrindimą.

Aptikus šį šabloną, galite greitai kurti ir analizuoti naujus algoritmus naudojant pasikartojimus.

Jis taip pat natūraliai susieja su lygiagrečiąja apdorojimu, nes nepriklausomos dalinės problemos gali vykdytis vienu metu.