14/04/2008
1
CHIA ĐỂ TRN
CHIA

ĐỂ

TRN
DIVIDE AND CONQUER
Phạm Thế Bảo
Khoa Toán – Tin học
Trường Đại học Khoa học Tự nhiên Tp.HCM
Nội dung
• Kỹ thuật quan trọng, đượcápdụng rộng rãi để
thiết
kế
các
giải
thuật
có
hiệu
quả
.
thiết
kế
các
giải
thuật
có
hiệu
quả

hiện. Ta gọinhững bài toán này là bài toán cơ sở.
Phạm Thế Bảo
14/04/2008
2
Mộtsố bài toán tiêu biểu
• MergeSort và QuickSort
ố
• Nhân s
ố
nguyên lớn
• Xếplịch thi đấuthể thao
• Bài toán con cân bằng
• …
Phạm Thế Bảo
MergeSort và QuickSort
• Chia tậpdữ liệulàm2tập con, quá trình chia
đế
khi
hỉ
ò
01
hầ
tử
Æ
dừ
(
bài
tá
đế
n

con
:
một
tập
sẽ
đứng
giữa
để
chia
thành
2
tập
con
:
một
tập
sẽ
có các phầntử có giá trị nhỏ hơn hay bằng, tập
còn lạisẽ có các phầntử có giá trị lớnhơn.
Phạm Thế Bảo
14/04/2008
3
Bài toán nhân hai số nguyên lớn
• Trong các ngôn ngữ lậptrình,kiểudữ liệusố
nguyên
đều
có
miền
giá
trị

tác
đi
kèm
là
:
cộng
,
trừ
,
nhân
,…
• Chúng ta xem xét cách nhân 02 số nguyên lớn
có n chữ số sao cho hiệuquả.
Phạm Thế Bảo
• Nếuchúngtadùngcáchnhânthôngthường,
nghĩalàtừng chữ số nhân với nhau rồicộng lại
thì chi phí là O(n
2
).
• Á
p
dụ
n
g
k
ỹ
t
h
uật
c

+B và Y=C10
n/2
+D
Ví dụ: A=1234 thì A=12x10
2
+34
Khi đóX.Y=AC10
n
+(AD+BC)10
n/2
+BD.
Giố
h
ê
l i
hi
iế
để
ó
bài
Giố
ng n
hư
tr
ê
nta
l
ạ
i
c

có thể thựchiện đơngiảnbằng cách thêm
nchữ số 0 Æ cũng cần O(n). GọiT(n)làthời
gian
nhân
hai
số
nguyên
lớn
ta
có
phương
gian
nhân
hai
số
nguyên
lớn
,
ta
có
phương
trình đệ quy:
Phạm Thế Bảo
• Giảiphương trình ta có T(n) =
Æ không cảithiện!
• Viếtlại:
XY AC10
n
+[(A
B)(D

p
hươn
g
trình đ
ệ
q
u
y
:
ập
ậ
g
ự
p g
ệ
qy
T(1)=1
T(n)=
Phạm Thế Bảo
Nghiệm?
14/04/2008
5
Nghiệmcủaphương trình T(n)=
Æ cảithiệnhơn.
Thuậtgiải thô:
longDigit multi2Integer(longDigit X, longDogit Y, int n){
if( 1) th t X*Y
if(
n=
1)

,n
/2)
;
m3=multi2Integer(B,D,n/2);
return (m1*10
n
+(m1+m2+m3)*10
n/2
+m3);
}
Phạm Thế Bảo
Xếplịch thi đấuthể thao
• Xét việcxếplịch thi đấu vòng tròn mộtlượt
cho
n
đội
đá
banh
Mỗi
đội
thi
đấu
với
nhau
cho
n
đội
đá
banh
.

n
í
tn
hấ
t
(
n-
1
)
ng
à
y.
Nếu
nlẻ thìtacóthể sắp (n-1)/2 cặpthiđấutrong
một ngày Æ cầnítnhất n ngày
Phạm Thế Bảo
14/04/2008
6
• Lịch thi đấulàmộtbảng n dòng và n-1 cộtvàđược
đánh số tứ 1trởđi, dòng i đạidiệnchođộithứ ivàcộtj
đạidiện cho ngày thi đấu j, ô(i,j) ghi độiphải thi đấu
với đội i trong ngày j.
• Dùng chiếnlượcchiađể trị: để sắplịch cho n đội, ta
sắ
p
cho n
/
2 đ
ộ
i

ucho2đội(
b
ài toán cơ
sở).
• Từ lịch thi đấucủa2đội, chúng ta sắplịch thi đấucho
4 độinhư sau:
– Lịch thi đấu cho 4 độilàmộtbảng 4 dòng 3 cột.
– Lịch thi đấu cho 2 đội 1 và 2 trong ngày 1 chính là lịch thi
đấu
của
2
đội
(
bài
toán
cơ
sở
)
Vậy
ô(
1
1
)=
2
ô(
2
1
)=
1
đấu

góc trên bên phải.
Phạm Thế Bảo
Ngày 1
Đội1 2
Đội2 1
Ngày 1 Ngày 2 Ngày 3
Đội1 2
Đội2 1
Đội3 4
Đội4 3
Ngày 1 Ngày 2 Ngày 3
Đội1 24
Đội2 13
Đội3 42
Đội4 31
Phạm Thế Bảo
Ngày 1 Ngày 2 Ngày 3
Đội1 234
Đội2 143
Đội3 412
Đội4 321
14/04/2008
7
Ngày 1 Ngày 2 Ngày 3 Ngày 4 Ngày 5 Ngày 6 Ngày 7
Đội1 234
Đ
ộ
i
2
1

2
1
4
3
Đội3 412
Đội4 321
Đội5 678
Đội6 587
Đội7 856
Đ
ộ
i
8
7
6
5
Đ
ộ
i
2
1
4
3
5
8
7
Đội3 412 85 6
Đội4 321 76 5
Đội5 678 23 4
Đội6 587 14 3

8
7
6
5
4
3
2
1
Phạm Thế Bảo
Đ
ộ
i
8
7
6
5
Đ
ộ
i
8
7
6
5
3
2
1
Đ
ộ
i
8

á
nconc
ó
kí
c
h
th
ư
ớ
cg
ầ
n
bằng nhau thì hiểusuấtsẽ cao hơn.
• Ví dụ:MergeSortchialàm2tậpconbằng
nhau (n/2 phầntử -cóthể sai khác 1) thì độ
phức
tạp
là
O
.
Đối
với
QuickSort
,
nếu
phức
tạp
là
O
.