Menene tsarin divide-and-conquer?

Question

Accepted Answer

**Divide and conquer** yana warware matsala ta hanyar (1) **rarraba** ta zuwa kananan matsaloli, (2) **cin gida** kowa sake-sake, da (3) **haduwa** da sakamako. Yawancin algorithms masu inganci suna bin wannan tsarin.

## Tunanin

Idan matsaloli ba su da dangantaka da suka ragu da sauri, jmlah aikin ya bi maimakon da kake iya tantancewa da **Master Theorem**.

## Misali: sikin element ta hanyar 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
```

## Misalai na classic

- **Merge sort / quicksort** — O(n log n) rangewa.
- **Binary search** — O(log n).
- **Saurin fasalwa, karatsuba multiplication, mafi kusanci juna.**

## Hadaddiyar

Yawancin lokaci T(n) = a·T(n/b) + f(n); don merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Lokacin amfani / kuskura

Amfani lokacin matsala **ta rarrabe mwajen** zuwa matsaloli ba tare da dangantaka ba. Idan matsaloli **su haduwa**, fi da amfani da dynamic programming maimakon haka (don kauce kauce). Girman maimakon kara da tarwatsi na haduwa zai iya isa wa gidan kan kananan bayani.

## Me yasa ya mahalaci

Divide and conquer wata takamaiman tsarin da ba za a iya sake amfani ba ta bayan wawajanya na yawa na algorithms masu inganci.

Sanin tsarin yana ba ka damar samun da bincika sabbin algorithms da sauri tare da maimakonan.

Hakanan ya zama jiya zuwa jiya akan jiya, dangane da matsaloli ba tare da dangantaka ba zai iya gudu daidai.