Bài giảng Thuật toán nâng cao - Chương 5: Chia để trị - Nguyễn Thanh Bình

Nguyên tắc

■ Nhiều thuật toán có cấu trúc đệ quy

□ Để giải quyết vấn đề đặt ra, thuật toán gọi lại chính nó để giải quyết các vấn đề con có kích thước nhỏ hơn, cuối cùng kết hỢp các kết quả thu được giải pháp

■ Gồm các bước

□ Chia: chia vấn đề thành các vấn đề con

□ Trị: giải quyết các vấn đề con một cách đệ quy, nếu vấn đề con có kích thước đủ nhỏ thì giải quyết trực tiếp

□ Kết hỢp: các kết quả của các vấn đề con là giải pháp cho vấn đặt ra