Bài giảng Phân tích và thiết kế giải thuật - Chương 2 Chiến lược chia-để-trị (Divide-and-conquer)

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 2

kích thước n/2

bài toán con 1

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

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ị” (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²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

Giải thuật căn bản của Quicksort

Quicksort là một phương pháp xếp thứ tự theo kiểu “chia

để trị”. Nó thực hiện bằng cách phân hoạch một tập tin

thành hai phần và sắp thứ tự mỗi phần một cách độc lập

với nhau.

Giải thuật có cấu trúc như sau:

procedure quicksort1(left,right:integer);

var i: integer;

begin

if right > left then

begin

i:= partition(left,right);

quicksort(left,i-1);

quicksort(i+1,right);

end;

6

Phân hoạch

Phần then chốt của Quicksort là thủ tục phân hoạch

(partition), mà sắp xếp lại mảng sao cho thỏa mãn 3 điều

kiện sau:

i) phần tử a[i] được đưa về vị trí đúng đắn của nó, với một

giá trị i nào đó,

ii) tất cả những phần tử trong nhóm a[left], ..., a[i-1] thì nhỏ

hơn hay bằng a[i]

iii) tất cả những phần tử trong nhóm a[i+1], ..., a[right] thì

lớn hơn hay bằng a[i]

Example:

8 59 56 52 55 58 51 57 54

52 51 53 56 55 58 59 57 54

7

Thí dụ về phân hoạch

Giả sử chúng ta chọn phần tử thứ nhất hay phần tử tận cùng

trái (leftmost ) như là phần tử sẽ được đưa về vị trí đúng của

nó ( Phần tử này được gọi là phần tử chốt - pivot).

40 15 30 25 60 10 75 45 65 35 50 20 70 55

40 15 30 25 20 10 75 45 65 35 50 60 70 55

40 15 30 25 20 10 35 45 65 75 50 60 70 55

35 15 30 25 20 10 40 45 65 75 50 60 70 55

nhỏ hơn 40

sorted lớn hơn 40

8

Giải thuật Quicksort

procedure quicksort2(left, right: integer);

var j, k: integer;

begin

if right > left then

begin

j:=left; k:=right+1;

//start partitioning

repeat

repeat j:=j+1 until a[j] >= a[left];

repeat k:=k-1 until a[k]<= a[left];

if j< k then swap(a[j],a[k])

until j>k;

swap(a[left],a[k]); //finish partitioning

quicksort2(left,k-1);

quicksort2(k+1,right)

end;

9

Phân tích độ phức tạp: trường hợp tốt nhất

Trường hợp tốt nhất xảy ra với Quicksort là khi mỗi lần

phân hoạch chia tập tin ra làm hai phần bằng nhau.

điều này làm cho số lần so sánh của Quicksort thỏa mãn hệ

thức truy hồi:

C_N= 2C_N/2+ N.

Số hạnh 2C_N/2là chi phí của việc sắp thứ tự hai nửa tập tin và

N là chi phí của việc xét từng phần tử khi phân hoạch lần

đầu.

Từ chương 1, việc giải hệ thức truy hồi này đã đưa đến lời

giải:

C_N≈ N lgN.

10

Phân tích độ phức tạp: trường hợp xấu nhất

Một trường hợp xấu nhất của Quicksort là khi tập tin đã có

thứ tự rồi.

Khi đó, phần tử thứ nhất sẽ đòi hỏi n so sánh để nhận ra

rằng nó nên ở đúng vị trí thứ nhất. Hơn nữa, sau đó phân

đoạn bên trái là rỗng và và phân đoạn bên phải gồm n – 1

phần tử. Do đó với lần phân hoạch kế, phần tử thứ hai sẽ

đòi hỏi n-1 so sánh để nhận ra rằng nó nên ở đúng vị trí thứ

hai. Và cứ tiếp tục như thế.

Như vậy tổng số lần so sánh sẽ là:

n + (n-1) + … + 2 + 1 = n(n+1)/2 =

(n²+ n)/2 = O(n²).

Độ phức tạp trường hợp xấu nhất của Quicksort là O(n²).

11

Độ phức tạp trường hợp trung bình của Quicksort

Công thức truy hồi chính xác cho tổng số so sánh mà Quick

sort cần để sắp thứ tự N phần tử được hình thành một cách

ngẫu nhiên:

N

C_N= (N+1) + (1/N) ∑ (C_k-1+ C_N-k)

1

với N ≥ 2 và C₁= C₀= 0

Số hạng (N+1) bao gồm số lần so sánh phần tử chốt với từng

phần tử khác, thêm hai lần so sánh để hai pointer giao nhau.

Phần còn lại là do sự kiện mỗi phần tử ở vị trí k có cùng xác

xuất 1/N để được làm phần tử chốt mà sau đó chúng ta có hai

phân đoạn với số phần tử lần lượt là k-1 và N-k.

12

Chú ý rằng, C₀+ C₁+ … + C_N-1thì giống hệt

C_N-1+ C_N-2+… + C₀, nên ta có

N

C_N= (N+1) + (1/N) ∑ 2C_k-1

1

Ta có thể loại trừ đại lượng tính tổng bằng cách nhân cả hai vế

với N và rồi trừ cho cùng công thức nhân với N-1:

NC_N– (N-1) C_N-1= N(N+1) – (N-1)N + 2C_N-1

Từ đó ta được

NC_N= (N+1)C_N-1+ 2N

13

Chia cả hai vế với N(N+1) ta được hệ thức truy hồi:

C_N/(N+1) = C_N-1/N + 2/(N+1)

= C_N-2/(N-1) + 2/N + 2/(N+1)

.

N

= C₂/3 + ∑ 2/(k+1)

3

N

C_N/(N+1) ≈ 2 ∑ 1/k ≈ 2 ∫ 1/x dx = 2lnN

1

Suy ra:

C_N≈ 2NlnN

14

Độ phức tạp trường hợp trung bình của

Quicksort (tt.)

Vì ta có:

lnN = (log₂N).(log_e2) =0.69 lgN

2NlnN ≈ 1.38 NlgN.

Tổng số so sánh trung bình của Quicksort chỉ khoảng

chừng 38% cao hơn trong trường hợp tốt nhất.

Mệnh đề. Quicksort cần khoảng 2NlnN so sánh trong

trường hợp trung bình.

15

3. Sắp thứ tự bằng cách trộn (mergesort)

Trước tiên, chúng ta xét một quá trình được gọi là trộn

(merging), thao tác phối hợp hai tập tin đã có thứ tự

thành một tập tin có thứ tự lớn hơn.

Trộn

Trong nhiều ứng dụng xử lý dữ liệu, ta phải duy trì

một tập dữ liệu có thứ tự khá lớn. Các phần tử mới

thường xuyên được thêm vào tập tin lớn.

Nhóm các phần tử được đính vào đuôi của tập tin lớn

và toàn bộ tập tin được sắp thứ tự trở lại.

Tình huống đó rất thích hợp cho thao tác trộn.

16

Trộn

Giả sử ta có hai mảng số nguyên có thứ tự a[1..M] và

b[1..N]. Ta muốn trộn chúng thành một mảng thứ ba

c[1..M+N].

i:= 1; j :=1;

for k:= 1 to M+N do

if a[i] < b[j] then

begin c [k] := a[i]; i:= i+1 end

else begin c[k] := b[j]; j := j+1 end;

Ghi chú: Giải thuật dùng a[M+1] và b[N+1] để làm phần

tử cầm canh chứa hai giá trị lớn hơn mọi trị khóa khác.

Nhờ chúng, khi một trong hai mảng đã cạn thì vòng lặp sẽ

đưa phần còn lại của mảng còn lại vào mảng c.

17

Sắp thứ tự bằng phương pháp trộn

Một khi ta đã có thủ tục trộn, ta dùng nó làm cơ sở để

xây dựng một thủ tục sắp thứ tự đệ quy.

Để sắp thứ tự một tập tin nào đó, ta chia thành hai

đoạn bằng nhau, sắp thứ tự hai đoạn này một cách

đệ quy và rồi trộn hai đoạn lại với nhau.

Mergesort thể hiện chiến lược thiết kế giải thuật theo

lối “Chia để trị” (divide-and-conquer).

Giải thuật sau sắp thứ tự mảng a[1..r], dùng mảng

b[1..r] làm trung gian,

18

procedure mergesort(1,r: integer);

var i, j, k, m : integer;

begin

if r-1>0 then

begin

m:=(r+1)/2; mergesort(1,m); mergesort(m+1,r);

for i := m downto 1 do b[i] := a[j];

for j :=m+1 to r do b[r+m+1-j] := a[j];

for k :=1 to r do

if b[i] < b[j] then

begin a[k] := b[i] ; i := i+1 end

else begin a[k] := b[j]; j:= j-1 end;

end;

19

A S O R T I N G E X A M P L E

Thí dụ: Sắp thứ tự một

mảng gồm những ký tự

chữ

A S

O R

A O R S

I T

G N

G I N T

A G I N O R S T

E X

A M

A E M X

L P

E L P

A E E L M P X

A A E E G I L M N O P R S T X

20

Bài giảng Phân tích và thiết kế giải thuật - Chương 2 Chiến lược chia-để-trị (Divide-and-conquer) - Dương Tuấn Anh