Tài liệu tham khảo thiết kế thuật toán - môn Khoa học máy tính | Thiết kế thuật toán Lê Sỹ Vinh Bộ môn Khoa Học Máy Tính - Khoa CNTT Đại Học Công Nghệ - ĐHQGHN Email vinhioi@ Chia đê trị Divide and Conquer Chia bài toán lớn thành các bài toán nhỏ cùng dạng với bài toán lớn nhưng có kích thước nhỏ hơn. Giải quyết các bài toán nhỏ độc lập Kết hợp nghiệm của nhửng bài toán nhỏ đê thu được bài toán lớn Ví dụ Merge sort Để sắp xếp một mảng A ta chia mảng A thành 2 mảng con A1 và A2. Sắp xếp A1 và A2 sau đó hòa nhập chúng thành một để được mang A đã sắp xếp. void MergeSort Item A int start int end if start end int mid start end 2 MergeSort A start mid MergeSort A mid 1 end Merge A start mid end
