Apa iku paradigma divide-and-conquer?

Question

Accepted Answer

**Divide and conquer** ngrampungake masalah kanthi (1) **ngbagi** dadi submasalah sing luwih cilik, (2) **ngrampungake** saben-saben kanthi rekursif, lan (3) **nggabungake** asiling. Akeh algoritma sing efisien ngikut template iki.

## Gagasane

Yen submasalah independen lan kecilne cepet, total karya ngikut pengulangan sing bisa dianalisis kanthi **Master Theorem**.

## Conto: unsur maksimal liwat 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
```

## Conto klasik

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

## Kompleksitas

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

## Kapan dienggo / jebakan

Gunakake nalika masalah **mbagi kanthi bersih** dadi submasalah independen. Yen submasalah **tumpang tindih**, luwih disenengi dynamic programming (kanggo ngindhari panghitung maneh). Overhead rekursi lan stepé nggabungake bisa dominan kanggo input cilik.

## Mengapa penting

Divide and conquer minangka blueprint sing bisa dienggo maneh ing mburi fraksi gedhé algoritma efisien.

Magenal pola iki ngidini sampeyan ngabdi lan nganalisis algoritma anyar kanthi cepet nganggo pengulangan.

Iki uga map alami ing parallelism, amarga submasalah independen bisa mlaku bebarengan.