Chia để trị (divide and conquer) là một chiến lược thiết kế thuật toán phổ biến bao gồm hai giai đoạn: chia (phân chia) và trị (hợp nhất), và thường được triển khai bằng đệ quy (recursion).
Tiêu chí xác định xem một bài toán có phải là bài toán chia để trị hay không bao gồm: bài toán có thể phân rã hay không, các bài toán con có độc lập với nhau hay không, và các bài toán con có thể hợp nhất hay không.
Sắp xếp trộn (merge sort) là một ứng dụng điển hình của chiến lược chia để trị. Nó chia một mảng (array) thành hai mảng con (subarray) có độ dài bằng nhau một cách đệ quy cho đến khi chỉ còn một phần tử (element), sau đó trộn chúng lại theo từng lớp để hoàn thành việc sắp xếp.
Việc áp dụng chiến lược chia để trị thường có thể nâng cao hiệu suất của thuật toán. Một mặt, nó giúp giảm số lượng phép toán; mặt khác, nó giúp việc tối ưu hóa song song bởi hệ thống trở nên dễ dàng hơn.
Chia để trị có thể giải quyết nhiều bài toán thuật toán và cũng được sử dụng rộng rãi trong thiết kế thuật toán và cấu trúc dữ liệu, điều này làm cho nó hiện diện ở khắp mọi nơi.
So với tìm kiếm vét cạn (brute-force search), tìm kiếm thích ứng (adaptive search) hiệu quả hơn. Các thuật toán tìm kiếm có độ phức tạp thời gian là \(O(\log n)\) thường được triển khai dựa trên chiến lược chia để trị.
Tìm kiếm nhị phân (binary search) là một ứng dụng điển hình khác của chia để trị. Nó không bao gồm bước hợp nhất lời giải của các bài toán con. Chúng ta có thể triển khai tìm kiếm nhị phân thông qua chia để trị đệ quy.
Trong bài toán dựng cây nhị phân (binary tree), việc dựng cây (bài toán ban đầu) có thể được chia thành dựng cây con trái (left subtree) và cây con phải (right subtree) (bài toán con), việc này có thể đạt được bằng cách chia các khoảng chỉ số của chuỗi duyệt tiền thứ tự và duyệt trung thứ tự.
Trong bài toán Hanota (Hanota problem), bài toán có quy mô \(n\) có thể được chia thành hai bài toán con quy mô \(n-1\) và một bài toán con quy mô \(1\). Sau khi giải quyết lần lượt ba bài toán con này, bài toán ban đầu sẽ được giải quyết.