Apa itu paradigma divide-and-conquer?

Question

Accepted Answer

**Divide and conquer** menyelesaikan masalah dengan (1) **membagi** masalah menjadi submasalah yang lebih kecil, (2) **menguasai** setiap masalah secara rekursif, dan (3) **menggabungkan** hasilnya. Banyak algoritma yang efisien mengikuti template ini.

## Idenya

Jika submasalah independen dan menyusut dengan cepat, pekerjaan total mengikuti rekurensi yang dapat Anda analisis dengan **Master Theorem**.

## Contoh: elemen maksimum melalui 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
```

## Contoh klasik

- **Merge sort / quicksort** — Penyortiran O(n log n).
- **Pencarian biner** — O(log n).
- **Pemangkatan cepat, perkalian Karatsuba, pasangan terdekat.**

## Kompleksitas

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

## Kapan digunakan / jebakan

Gunakan ketika masalah **terbagi dengan bersih** menjadi submasalah independen. Jika submasalah **tumpang tindih**, lebih suka pemrograman dinamis sebagai gantinya (untuk menghindari penghitungan ulang). Overhead rekursi dan langkah penggabungan dapat mendominasi untuk input kecil.

## Mengapa ini penting

Divide and conquer adalah blueprint yang dapat digunakan kembali di balik sebagian besar algoritma yang efisien.

Mengenali pola memungkinkan Anda menurunkan dan menganalisis algoritma baru dengan cepat menggunakan rekurensi.

Ia juga memetakan secara alami ke paralelisme, karena submasalah independen dapat berjalan secara bersamaan.