.png)
Thuật toán chia để trị (Divide and conquer algorithm)
Thuật toán chia để trị (Divide and conquer algorithm)
o Nội dung thuật toán:
Ðể giải một bài toán kích thước n, ta chia bài toán đã cho thành một số bài toán con có kích thưóc nhỏ hơn. Giải các bài toán con này rồi tổng hợp kết quả lại để được lời giải của bài toán ban đầu.
Ðối với các bài toán con, chúng ta lại sử dụng kỹ thuật chia để trị để có được các bài toán kích thước nhỏ hơn nữa. Quá trình trên sẽ dẫn đến những bài toán mà lời giải chúng là hiển nhiên hoặc dễ dàng thực hiện, ta gọi các bài toán này là bà itoán cơ sở
Nội dung thuật toán gồm 3 thànhphần:
- Chia: phân tích bài toán có N thành phần dữ liệu thành nhiều bài toán con có kích thước dữ liệu nhỏ hơn
- Trị: giải bài toán con bằng phương pháp đệ quy. Tuy nhiên nếu bài toán con đủ nhỏ, có thể giải quyết theo cách đơn giản
- Tổng hợp: tổng hợp nghiệm của các bài toán con thành nghiệm của bài toán ban đầu
o Các bài toán phổ biến sử dụng thuật toán chia để trị
1) Sắp xếp kiểu trộn (Merge sort)
2) Tìm kiếm nhị phân (Binary search)
3) Sắp xếp nhanh (Quick sort)
4) Nhân các số nguyên lớn
5) Xếp lịch thi đấu thể thao
6) Tìm phần tử lớn nhất của mảng
7) Tìm phần tử trung bình của mảng
8) Tìm dãy con có tổng lớn nhất
9) Tìm cặp điểm gần nhau nhất
10) Phủ bàn cờ Tromino
Ví dụ: Sắp xếp kiểu trộn (Merge Sort)
Cho 1 dãy số M có N phần tử nguyên. Viết thuật toán sắp xếp dãy số M tăng dần
Chia: phân chia dãy N phần tử sẽ được sắp xếp thành 2 dãy con, mỗi dãy có N/2 phần tử
Trị: dùng kỹ thuật trộn 2 dãy con đã được sắp xếp thành dãy kết quả được sắp xếp. Quá trình này xảy ra khi các dãy con không thể phân chia được nữa
Tổng hợp: tổng hợp kết quả của 2 dãy con đã được sắp xếp thành dãy được sắp xếp
Độ phức tạp thuật toán: O(n logn)
Giả sử muốn sắp xếp dãy con M có k phần tử, các phần tử có chỉ số từ low đến high
Thuật toán sắp xếp (M, low, high) như sau:
Nếu low<high thì
mid = (low+high)/2
Gọi đệ quy sắp xếp nửa trước của dãy M có chỉ số từ low đến mid
Gọi đệ quy sắp xếp nửa sau của dãy M có chỉ số từ mid+1 đến high
Trộn 2 dãy con tăng thành dãy ban đầu
public void sapXep(int[] M, int low; int high){
if (low<high) {
mid=(low+high) / 2;
sapXep(M, low, mid);
sapXep(M, mid+1, high);
tron(M, low, mid, high);
}
}
tron(): trộn 2 dãy con tăng thành một dãy con tăng
0 nhận xét: