Cơ bản về thuật toán chia để trị

Chia để trị là một kỹ thuật thiết kế thuật toán bao gồm việc chia một bài toán cần giải ra thành những bài toán con nhỏ hơn có cùng một loại vấn đề, giải từng bài toán con đó một cách lần lượt và độc lập, sau đó kết hợp các lời giải con thu được nhờ cách đó để thu được lời giải của bài toán nguyên thuỷ. Hai câu hỏi tự nhiên nảy ra là “Vì sao ai đó làm việc này?” và “Chúng ta cần giải các bài toán con như thế nào?”. Tính hiệu quả của kỹ thuật chia để trị nằm ở câu trả lời cho câu hỏi thứ hai.