Bài giảng Thuật toán ứng dụng - Chương 4: Chia để trị - Phạm Quang Dũng
NộI dung
Tổng quan chia để trị
Ví dụ minh họa
Độ phức tạp chia để trị
Giảm để trị
2
Tổng quan chia để trị
Chia bài toán cần giải ban đầu thành các bài toán con
độc lập nhau
Giải (trị) các bài toán con
Tổng hợp lời giải của các bài toán con để dẫn ra lời
giải của bài toán xuất phát
3
Ví dụ minh họa
Bài toán dãy con dài nhất: cho dãy số nguyên a = a1,
a2, …, an. Tìm dãy con gồm một số liên tiếp các phần
tử có tổng lớn nhất
Phân chia: ký hiệu P(i, j) là lời giải của bài toán tìm dãy
con liên tiếp của dãy ai, ai+1,…, aj có tổng cực đại
Tổng hợp lời giải
Ký hiệu PL(i, j) là lời giải của bài toán tìm dãy con liên tiếp
của dãy ai, ai+1,…, aj sao cho phần tử cuối cùng là aj có
tổng cực đại
Ký hiệu PR(i, j) là lời giải của bài toán tìm dãy con liên
tiếp của dãy ai, ai+1,…, aj sao cho phần tử đầu tiên là ai
có tổng cực đại
4
Ví dụ minh họa
Xét đoạn [l,l+1,...,r]. Ký hiệu m = (l+r)/2
P(l,r) = MAX{P(l, m), P(m+1,r), PL(l,m) + PR(m+1,r)}
P(l,m)
P(m+1,r)
l
r
m m+1
PR(m+1,r)
PL(l,m)
5
Ví dụ minh họa
#include <bits/stdc++.h>
using namespace std;
#define INF 1e9
#define MAX 1000000
int a[MAX];
int n;
void input(){
cin >> n;
for(int i = 0; i < n; i++) cin >> a[i];
}
6
Ví dụ minh họa
int PL(int l, int r){
int rs = -INF;
int s = 0;
for(int i = r; i >= l; i--){
s += a[i];
rs = max(rs,s);
}
return rs;
}
int PR(int l, int r){
int rs = -INF;
int s = 0;
for(int i = l; i <= r; i++){
s += a[i];
rs = max(rs,s);
}
return rs;
}
7
Ví dụ minh họa
int P(int l, int r){
if(l == r) return a[r];
int m = (l+r)/2;
return max(max(P(l,m),P(m+1,r)), PL(l,m)+PR(m+1,r));
}
void solve(){
cout << P(0,n-1);
}
int main(){
input();
solve();
}
8
Độ phức tạp tính toán
procedure D-and-C(n) {
Chia bài toán xuất phát thành a bài
toán con, mỗi bài toán con kích
1. if(n n0)
thước n/b
2.
xử lý trực tiếp
T(n): thời gian của bài toán kích
thước n
3. else{
4.
chia bài toán xuất phát
Thời gian phân chia (dòng 4): D(n)
thành a bài toán con kích thước
n/b
Thời gian tổng hợp lời giải (dòng 6):
C(n)
5.
gọi đệ quy a bài toán con
6.
tổng hợp lời giải
Công thức truy hồi:
7. }
}
Q 1 ,
ꢀ ≤ ꢀ0
T ꢀ = ꢁ
ꢄ
ꢂꢃ
+ ꢆ ꢀ + ꢇ ꢀ , ꢀ > ꢀ0
ꢅ
9
Độ phức tạp tính toán
Độ phức tạp của thuật toán chia để trị (định lí thợ)
Công thức truy hồi:
T(n) = aT(n/b) + cnk, với các hằng số a 1, b > 1, c > 0
Nếu a > bk thì T(n) = Q(ꢀꢈꢉꢊ ꢌ
)
ꢋ
Nếu a = bk thì T(n) = Q(ꢀꢍꢎꢏꢐꢀ) với logn = ꢎꢏꢐꢑꢀ
Nếu a < bk thì T(n) = Q(ꢀꢍ)
10
Độ phức tạp tính toán
Độ phức tạp của thuật toán chia để trị (định lí thợ)
Công thức truy hồi:
T(n) = aT(n/b) + cnk, với các hằng số a 1, b > 1, c > 0
Nếu a > bk thì T(n) = Q(ꢀꢈꢉꢊ ꢌ
)
ꢋ
Nếu a = bk thì T(n) = Q(ꢀꢍꢎꢏꢐꢀ) với logn = ꢎꢏꢐꢑꢀ
Nếu a < bk thì T(n) = Q(ꢀꢍ)
Thuật toán chia để trị giải bài toán tổng con cực đại có
độ phức tạp là O(nlogn)
11
Sắp xếp trộn
Phân chia: Chia dãy a1, …, an thành 2 dãy con có độ dài bằng
nhau
Trị đệ quy: Sắp xếp 2 dãy con bằng thuật toán sắp xếp trộn
Tổng hợp: Trộn 2 dãy con đã được sắp với nhau để thu được
dãy ban đầu được sắp thứ tự
12
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
3
8
9
20
4
5
10 11 23
a
k
ta
13
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
1
3
8
9
20
4
5
10 11 23
a
k
ta
14
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
1
3
3
8
9
20
4
5
10 11 23
a
k
ta
15
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
1
3
3
8
9
20
4
5
10 11 23
a
k
4
ta
16
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
1
3
3
8
9
5
20
4
5
10 11 23
a
k
4
ta
17
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
1
3
3
8
4
9
20
4
5
10 11 23
a
k
5
8
ta
18
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
1
3
3
8
4
9
5
20
4
9
5
10 11 23
a
k
8
ta
19
Sắp xếp trộn
Trộn hai dãy đã được sắp xếp thành dãy mới được sắp
xếp
i
j
1
1
3
3
8
4
9
5
20
4
9
5
10 11 23
a
k
8
10
ta
20
Tải về để xem bản đầy đủ
31 trang
15780
Free
Bạn đang xem 20 trang mẫu của tài liệu "Bài giảng Thuật toán ứng dụng - Chương 4: Chia để trị - Phạm Quang Dũng", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- bai_giang_thuat_toan_ung_dung_chuong_4_chia_de_tri_pham_quan.pdf
