1
Ch ng 2ươ
Chi n l c chia-đ -tr ế ượ ể ị
(Divide-and-conquer)
2
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ế ị
3
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.ế ấ ủ ế ượ
4
bài toán kích th c nướ
bài toán con 1
kích th c n/2ướ
bài toán con 2
kích th c n/2ướ
l i gi i cho ờ ả
bài toán con 1 l i gi i cho ờ ả
bài toán con 2
l i gi i cho bài toán ban đ uờ ả ầ
Chi n l c chia-đ -trế ượ ể ị
5
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ể ị” (divide-and-conquer).
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 Nầ ả 2 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).ễ ị ỗ ậ
