Xem mẫu
Chương 2
Chiến lược chia-để-trị (Divide-and-conquer)
1
Nội dung
1. Chiến lược chia để trị 2. Quicksort
3. Xếp thứ tự bằng phương pháp trộn 4. Xếp thứ tự ngoại
5. Cây tìm kiếm nhị phân
2
Chiến lược chia-để-trị
Là chiến lược thiết kế giải thuật nổi tiếng nhất.
Các giải thuật chia-để-trị thường tiến hành theo các bước sau:
Thể hiện của bài toán được chia làm những thể hiện nhỏ hơn.
Những thể hiện nhỏ hơn này được giải quyết (thường là đệ quy, mặc dù đôi khi không cần đệ quy).
Những lời giải đạt được từ những thể hiện nhỏ hơn phối hợp lại làm thành lời giải của bài toán ban đầu.
Tìm kiếm bằng p.p. chia đôi (binary search) là một thí dụ của chiến lược chia-để-trị.
Sơ đồ sau mô tả một chiến lược chia-để-trị mà trong đó chia bài toán thành hai bài toán nhỏ hơn. Đây là trường hợp phổ biến nhất của chiến lược này.
3
Chiến lược chia-để-trị
bài toán kích thước n
bài toán con 1 kích thước n/2
lời giải cho bài toán con 1
bài toán con 2 kích thước n/2
lời giải cho bài toán con 2
lời giải cho bài toán ban đầu
4
2. Giải thuật Quick sort
Giải thuật căn bản của Quick sort được phát minh năm 1960 bởi C. A. R. Hoare.
Quicksort thể hiện tinh thần thiết kế giải thuật theo lối “Chia để trị” (divideandconquer).
Quicksort được ưa chuộng vì nó không quá khó để hiện thực hóa.
Quicksort chỉ đòi hỏi khoảng chừng NlgN thao tác căn bản để sắp thứ tự N phần tử.
Nhược điểm của Quick sort gồm: Nó là một giải thuật đệ quy
Nó cần khoảng N2 thao tác căn bản trong trường hợp xấu nhất
Nó dễ bị lỗi khi lập trình (fragile).
5
...
- tailieumienphi.vn
nguon tai.lieu . vn