X'inhu l-paradigma ta' taqsim-u-ikkunssta?

Question

Accepted Answer

**Taqsim u ikkunssta** issolvi problema billi (1) **taqsammha** f'sub-problemi iżgħar, (2) **tikkunsstahhom** kull wieħed b'mod rikursiv, u (3) **tgħaqqadha** r-riżultati. Ħafna algoritmi effiċjenti jsegwu dan it-template.

## L-idea

If sub-problemi huma indipendenti u jaqgħu malajr, ix-xogħol totali isegwi rikorrenza li tista' tanalizza bit-**Teorema ta' Master**.

## Eżempju: element massimu permezz ta' taqsim-u-ikkunssta

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

## Eżempji klassiċi

- **Merge sort / quicksort** — sortir O(n log n).
- **Tfittxija binarja** — O(log n).
- **Esponenzjazzjoni mabda', multiplikazzjoni Karatsuba, par l-eqreb.**

## Kumplessità

Spiss T(n) = a·T(n/b) + f(n); għal merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Meta tuża / ħbiebi

Uża meta problema **tinqasam b'mod ċar** f'sub-problemi indipendenti. Jekk sub-problemi **joħxdu**, prefer il-programmazzjoni dinamika minflok (biex tiġib il-kalkolu mill-ġdid). L-overhead tal-rikursjoni u l-pass tal-magħluq jistgħu jiddomoraw għal inputs żgħar.

## Għaliex importanti

Taqsim u ikkunssta hija blueprint li tista' tintuża mill-ġdid wara frazzjoni kbira ta' algoritmi effiċjenti.

Il-ħsieb tal-pattern iletin tiddividi u tanalizza algoritmi ġodda b'aħfef bit-rikorrenze.

Ihidden jinqasmu naturalment għall-paralleliżmu, billi sub-problemi indipendenti jistgħu jaħdmu flimkien.