Tổng quan
Chia để trị là kỹ thuật chia một bài toán thành các bài toán con độc lập nhỏ hơn, giải đệ quy từng cái, rồi kết hợp lời giải. Tìm giá trị lớn nhất của mảng bằng cách cắt đôi nó là ví dụ tối giản, rõ ràng.
Cùng khuôn mẫu chia → trị → gộp này là nền tảng của những thuật toán mạnh như Merge Sort và Quick Sort, nên nắm vững nó ở đây mang lại lợi ích rộng khắp.
Chia để trị hoạt động thế nào?
- Chia: cắt đoạn hiện tại làm đôi tại điểm giữa.
- Trường hợp cơ sở: đoạn chỉ một phần tử chính là giá trị lớn nhất của nó, trả về trực tiếp.
- Trị: đệ quy tìm giá trị lớn nhất của nửa trái và của nửa phải.
- Gộp: đáp án cho đoạn là giá trị lớn hơn trong hai cực đại nửa.
Khi nào nên dùng?
- Sắp xếp (Merge Sort, Quick Sort) và tìm kiếm (tìm kiếm nhị phân) trên đầu vào chia được.
- Các bài toán song song hóa tốt, vì các bài toán con độc lập chạy đồng thời.
- Ưu tiên duyệt tuyến tính đơn giản khi bước gộp tốn kém ngang với giải trực tiếp.
Phân tích độ phức tạp
Với bài toán cực đại, mỗi phần tử được xét đúng một lần qua đệ quy và bước gộp là O(1), cho tổng thời gian O(n) — hệ thức T(n) = 2T(n/2) + O(1) giải ra O(n). Độ sâu đệ quy là O(log n), nên bộ nhớ ngăn xếp là O(log n).
Câu hỏi thường gặp
Ba giai đoạn của chia để trị là gì?
Chia bài toán thành các bài toán con, trị từng bài toán con bằng đệ quy, rồi gộp các lời giải con thành kết quả cuối. Bước trộn của Merge Sort là một ví dụ gộp kinh điển.
Chia để trị có luôn nhanh hơn vòng lặp thường không?
Không. Với việc tìm cực đại nó vẫn O(n) như vòng lặp, lại thêm chi phí đệ quy. Nó thắng thế khi việc chia biến công việc O(n²) thành O(n log n), như trong sắp xếp.