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

Chia để trị (Divide and Conquer)

B Nguyên tắc - Nhiều thuật toán có cấu trúc đệ quy | 0 Đế 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

3 Chia: chia vấn đề thành các vấn đề con g 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 0 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