Mô thức divide-and-conquer là gì?

Question

Accepted Answer

**Divide and conquer** giải một bài toán bằng cách (1) **chia** nó thành các bài toán con nhỏ hơn, (2) **chinh phục** mỗi bài toán con bằng đệ quy, và (3) **kết hợp** các kết quả. Nhiều thuật toán hiệu quả tuân theo khuôn mẫu này.

## Ý tưởng

Nếu các bài toán con độc lập và thu nhỏ nhanh, tổng khối lượng công việc tuân theo một hệ thức truy hồi mà bạn có thể phân tích bằng **Master Theorem**.

## Ví dụ: tìm phần tử lớn nhất bằng divide and conquer

```python
def max_dc(arr, lo, hi):
    if lo == hi:                       # base case: một phần tử
        return arr[lo]
    mid = (lo + hi) // 2
    left = max_dc(arr, lo, mid)        # chinh phục bên trái
    right = max_dc(arr, mid + 1, hi)   # chinh phục bên phải
    return max(left, right)            # kết hợp

max_dc([3, 9, 2, 7], 0, 3)            # -> 9
```

## Các ví dụ kinh điển

- **Merge sort / quicksort** — sắp xếp O(n log n).
- **Binary search** — O(log n).
- **Lũy thừa nhanh, nhân Karatsuba, cặp điểm gần nhất.**

## Độ phức tạp

Thường là T(n) = a·T(n/b) + f(n); với merge sort, T(n) = 2T(n/2) + O(n) = **O(n log n)**.

## Khi nào dùng / những cạm bẫy

Dùng khi một bài toán **tách ra gọn gàng** thành các bài toán con độc lập. Nếu các bài toán con **chồng lấn**, hãy ưu tiên dynamic programming thay thế (để tránh tính lại). Chi phí đệ quy và bước kết hợp có thể chiếm ưu thế với đầu vào nhỏ.

## Tại sao điều này quan trọng

Divide and conquer là một bản thiết kế có thể tái sử dụng đứng sau một phần lớn các thuật toán hiệu quả.

Nhận ra mô thức này cho phép bạn suy ra và phân tích các thuật toán mới một cách nhanh chóng bằng các hệ thức truy hồi.

Nó cũng ánh xạ tự nhiên sang xử lý song song, vì các bài toán con độc lập có thể chạy đồng thời.