Apakah paradigma bagi-dan-takluk?

Question

Accepted Answer

**Bagi dan takluk** menyelesaikan masalah dengan (1) **membagi** masalah kepada sub-masalah yang lebih kecil, (2) **menaklukkan** setiap satu secara rekursif, dan (3) **menggabungkan** hasilnya. Banyak algoritma yang cekap mengikuti template ini.

## Idenya

Jika sub-masalah adalah bebas dan menyusut dengan cepat, jumlah kerja keseluruhan mengikuti pengulangan yang dapat anda analisis dengan **Teori Master**.

## Contoh: elemen maksimal melalui bagi-dan-takluk

```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** — pengurutan O(n log n).
- **Pencarian binari** — O(log n).
- **Eksponen cepat, perkalian Karatsuba, pasangan terdekat.**

## Kerumitan

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** ke dalam sub-masalah bebas. Jika sub-masalah **bertindihan**, lebih suka pemrograman dinamis sebagai gantinya (untuk menghindari perhitungan ulang). Overhead rekursi dan langkah gabung dapat menguasai untuk input kecil.

## Mengapa penting

Bagi dan takluk adalah blueprint yang dapat digunakan kembali di balik sebagian besar algoritma yang cekap.

Mengenali pola ini memungkinkan anda untuk menurunkan dan menganalisis algoritma baru dengan cepat menggunakan pengulangan.

Ia juga memetakan secara alami ke paralelisme, karena sub-masalah bebas dapat dijalankan bersamaan.