Buzz
Trong lĩnh vực khoa học máy tính, chia để trị là một chiến lược thiết kế thuật toán quan trọng dựa trên phương pháp đệ quy với nhiều bước phân chia. Thuật toán này hoạt động bằng cách tách bài toán lớn thành nhiều bài toán nhỏ hơn cùng loại, tiếp tục như vậy cho đến khi bài toán trở nên đủ đơn giản để giải quyết dễ dàng. Sau đó, các kết quả từ các bài toán nhỏ được kết hợp lại để giải quyết bài toán gốc.
Kỹ thuật này là nền tảng cho nhiều thuật toán hiệu quả, như các thuật toán sắp xếp (sắp xếp nhanh, sắp xếp trộn), thuật toán nhân (thuật toán Karatsuba), phân tích cú pháp và biến đổi Fourier rời rạc.
Tuy nhiên, việc hiểu và thiết kế thuật toán chia để trị là một kỹ năng cần nhiều thời gian để thành thạo. Tương tự như chứng minh quy nạp, đôi khi cần thay thế bài toán gốc bằng một bài toán tổng quát hơn để thiết lập mối liên hệ đệ quy. Không có phương pháp hệ thống nào để tìm bài toán tổng quát phù hợp trong mọi tình huống.
Tên gọi 'chia để trị' cũng có thể áp dụng cho các thuật toán chuyển bài toán gốc thành một bài toán nhỏ hơn, như thuật toán tìm kiếm nhị phân, dùng để tìm khóa trong danh sách đã sắp xếp. Những thuật toán này có thể được lập trình hiệu quả hơn các thuật toán chia để trị truyền thống: đặc biệt, nếu chúng sử dụng đệ quy đuôi, có thể chuyển thành vòng lặp thay vì đệ quy. Do đó, một số tác giả cho rằng tên 'chia để trị' nên được dùng cho trường hợp bài toán có thể được chia thành hai hoặc nhiều bài toán nhỏ hơn. Có người đề xuất tên 'giảm để trị' cho trường hợp quy về đúng một bài toán nhỏ hơn.
Để chứng minh tính chính xác của thuật toán chia để trị, người ta thường sử dụng phương pháp quy nạp. Thời gian thực thi của chúng thường được xác định qua các hệ thức truy hồi.
Các ví dụ tiêu biểu
Một ví dụ cổ điển về thuật toán chia để trị là thuật toán Cooley-Tukey dùng cho biến đổi Fourier rời rạc. Thuật toán này được Gauss phát hiện vào năm 1805, nhưng ông không phân tích số phép toán, và chỉ sau hơn một thế kỉ, thuật toán này mới được phổ biến rộng rãi khi được phát hiện lại.
Một ví dụ lâu đời khác là thuật toán sắp xếp trộn, được John von Neumann phát minh vào năm 1945.
Một ví dụ quan trọng khác là thuật toán của Anatolii A. Karatsuba phát hiện vào năm 1960, dùng để nhân hai số nguyên có n chữ số trong phép toán. Thuật toán này đã bác bỏ giả thuyết của Andrey Kolmogorov năm 1956 rằng việc nhân hai số nguyên n chữ số cần ít nhất phép toán.
