Paradigmu ya "divide-and-conquer" ni nini?

Question

Accepted Answer

**Divide and conquer** husoma tatizo kwa (1) **kugawanya** katika tatizo ndogo, (2) **kushinda** kila moja kwa njia ya kurudia, na (3) **kuchanganya** matokeo. Algorithms nyingi zenye ufanisi zinafuata muundo huu.

## Wazo

Kama tatizo ndogo zina uhuru na zinakula haraka, kazi ya jumla inafuata muundo wa kurudia ambao unaweza kuchambua kwa **Master Theorem**.

## Mfano: kipengele cha juu kupitia divide and conquer

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

## Mifano ya jadi

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

## Utata

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

## Wakati wa kutumia / hatari

Tumia wakati tatizo **linagawanywa vizuri** katika tatizo ndogo lenye uhuru. Ikiwa tatizo ndogo **linaingiliana**, pendelea dynamic programming badala yake (kuepuka kuhesabu tena). Kukamatia kwa kurudia na hatua ya kuchanganya inaweza kuwa nyingi kwa ingizo ndogo.

## Kwa nini ina maana

Divide and conquer ni mpango wa kubadilika unaonacho katika sehemu kubwa ya algorithms zenye ufanisi.

Kutambua muundo hukuruhusu kuhanga na kuchambua algorithms mpya haraka kwa muundo wa kurudia.

Inakamatia kwa asili kwenye parallelism, kwa sababu tatizo ndogo lenye uhuru linaweza kukimbia kwa sambamba.