Çfarë është paradigma e ndarjes dhe pushtimit?

Question

Accepted Answer

**Ndarja dhe pushtimi** zgjidh një problem duke (1) **ndarë** atë në nënproblema më të vogla, (2) **pushtuar** secilën në mënyrë rekurzive, dhe (3) **kombinuar** rezultatet. Shumë algoritme efikase ndjekin këtë shabllon.

## Ideja

Nëse nënproblemat janë të pavarura dhe zvogëlohen shpejt, puna totale ndjek një recurrencë që mund ta analizoni me **Teoremën Kryesore**.

## Shembull: elementi maksimal përmes ndarjes dhe pushtimit

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

## Shembuj klasikë

- **Merge sort / quicksort** — O(n log n) sortim.
- **Binary search** — O(log n).
- **Eksponentimi i shpejtë, shumëzimi Karatsuba, palë më të afërta.**

## Kompleksiteti

Shpesh T(n) = a·T(n/b) + f(n); për merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Kur ta përdorni / grackat

Përdorni kur një problem **ndahet qartë** në nënproblema të pavarura. Nëse nënproblemat **mbivendosen**, preferoni programmimin dinamik në vend të tij (për të shmangur rillogaritjen). Prania e rekursionit dhe hapi i kombinimit mund të dominojnë për inpute të vogla.

## Pse ka rëndësi

Ndarja dhe pushtimi është një shabllon i riundësueshëm pas një fraksioni të madh të algoritmeve efikase.

Përkujtimi i modelit ju lejon të nxirrni dhe analizoni algoritme të reja me shpejtësi me anë të recurrencëve.

Ai gjithashtu hartohet natyrshëm në paralelizëm, pasi nënproblemat e pavarura mund të ekzekutohen njëkohësisht.