Phân tích và thiết kế giải thuật: Phân tích độ phức tạp của một số giải thuật sắp thự tự và tìm kiếm - Chương 2

Chia sẻ: Nguyen Bac A. Châu | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

293
lượt xem 106
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài Giảng điện tử Phân tích và thiết kế giải thuật. Tiến sĩ Dương Tuấn Anh. Chương 2: Phân tích độ phức tạp của một số giải thuật sắp thứ tự và tìm kiếm. Xét những phương pháp sắp thứ tự một tập tin gồm các mẫu tin có chứa khoá. Khoá mà lại 1 phần của mẫu tin, được dùng để điều khiển việc sắp thứ tự.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Phân tích và thiết kế giải thuật: Phân tích độ phức tạp của một số giải thuật sắp thự tự và tìm kiếm - Chương 2

Ch ng 2 Phân tích ph c t p c a m t s gi i thu t s p th t và tìm ki m 1
N i dung 1. Vài ph ng pháp s p th t c n b n 2. Quicksort 3. X p th t d a vào c s 4. X p th t b ng ph ng pháp tr n 5. X p th t ngo i 6. Vài ph ng pháp tìm ki m c n b n 2
Nguyên t c v s p th t Xét nh ng ph ng pháp s p th t m t t p tin g m các m u tin (record) có ch a khóa (key). Khóa mà là m t ph n c a m u tin, c dùng i u khi n vi c s p th t . M c tiêu: s p x p các m u tin sao cho các tr khóa c a chúng có th t theo m t qui lu t th t nào ó. N u các t p tin c s p th t có th ch a trong b nh chính thì gi i thu t s p th t c g i là s p th t n i (internal sorting). Vi c s p th t t p tin l u b nh ph c g i là s p th t ngo i (external sorting). 3
Hai nhóm ph ng pháp s p th t Chúng ta quan tâm n th i gian tính toán c a các gi i thu t s p th t . 1. M t nhóm g m 4 ph ng pháp c n b n òi h i th i gian tính toán t l v i N2 s p th t N ph n t . 2. Các ph ng pháp tiên ti n h n có th s p th t N ph n t trong th i gian ch y t l v i NlgN. M t c tính c a ph ng pháp s p th t là tính n nh (stability). M t ph ng pháp s p th t c g i là n nh khi nó b o toàn c th t t ng i c a các ph n t cùng tr khóa trong t p tin. 4
1. Nhóm ph ng pháp c n b n V i nhóm này, có hai ph ng pháp s p th t c ch n kh o sát: - s p th t b ng ph ng pháp ch n (selection sort) - s p th t b ng ph ng pháp chèn (insertion sort) V i m c ích t p trung vào khía c nh gi i thu t, ta s làm vi c v i các ph ng pháp mà nó ch s p th t các m ng s nguyên theo th t l n d n c a s . 5
S p th t b ng ph ng pháp ch n Ý t ng: “Tr c tiên tìm ph n t nh nh t trong m ng và hoán i nó v i ph n t ang v trí th nh t trong m ng, và r i tìm ph n t nh th nhì trong m ng và hoán i nó v i ph n t ang v trí th nhì trong m ng, và c th cho n khi toàn m ng ã c s p th t .” 390  45 45 45 45 205 205  182 182 182 182 182 205  205 205 45 390 390 390  235 235 235 235 235 390 6
Gi i thu t s p th t b ng ph ng pháp ch n procedure selection; var i, j, min, t: integer; begin for i :=1 to N-1 do begin min :=i; for j :=i+1 to N do if a[j]
Phân tích ph c t p c a selection sort Vòng l p trong (tác v so sánh) c th c hi n v i t ng s l n nh sau: (N-1)+(N-2)+...+1 =N(N-1)/2 =O(N2) Vòng l p ngoài c th c thi N-1 l n. Tính ch t 1.1: Selection sort th c thi kho ng N hoán v và N2/2 so sánh. Ghi chú: Th i gian tính toán c a selection sort thì c l p i v i d li u nh p. 8
S p th t b ng ph ng pháp chèn Ý t ng : Gi i thu t xem xét t ng ph n t m t, chèn nó vào v trí úng c a nó trong nhóm các ph n t ã c s p th t r i. 390 205 182 45 45 205 390 205 182 182 182 182 390 205 205 45 45 45 390 235 235 235 235 235 390 9
Gi i thu t s p th t b ng ph ng pháp chèn procedure insertion; var i; j; v:integer; begin for i:=2 to N do begin v:=a[i]; j:= i; while a[j-1]> v do begin a[j] := a[j-1]; // pull down j:= j-1 end; a[j]:=v; end; end; 10
Nh ng l ý v gi i thu t insertion sort 1. Chúng ta dùng m t tr khóa “c m canh” (sentinel) t i a[0], làm cho nó nh h n ph n t nh nh t trong m ng. 2. Vòng l p ngoài c a gi i thu t c th c thi N-1 l n. Tr ng h p x u nh t x y ra khi m ng ã có th t o ng c. Khi ó, vòng l p trong c th c thi v i t ng s l n sau ây: (N-1) + (N-2) + ... + 1 =N(N-1)/2 =O(N2) S b c chuy n = N(N-1)/2 S so sánh = N(N-1)/2 3. Trung bình có kho ng ch ng (i-1)/2 so sánh c th c thi trong vòng l p trong. Do ó, trong tr ng h p trung bình, t ng s l n so sánh là: (N-1)/2 + (N-2)/2 + ... + 1/2 =N(N-1)/4 =O(N2) 11
ph c t p c a s p th t b ng ph ng pháp ch n và ph ng pháp chèn Tính ch t 1.2: S p th t b ng ph ng pháp ch n th c thi kho ng N2/2 so sánh và N2/4 hoán v trong tr ng h p x u nh t. Tính ch t 1.3: S p th t b ng ph ng pháp chèn th c thi kho ng N2/4 so sánh và N2/8 hoán v trong tr ng h p trung bình. Tính ch t 1.4: S p th t b ng ph ng pháp chèn có ph c t p tuy n tính i v i m t m ng ã g n có th t . 12
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 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 N2 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). 13
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; end; 14
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: 53 59 56 52 55 58 51 57 54 52 51 53 56 55 58 59 57 54 15
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 16
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]k; swap(a[left],a[k]); //finish partitioning quicksort2(left,k-1); quicksort2(k+1,right) end; end; 17
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: CN = 2CN/2 + N. S h nh 2CN/2 là 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: CN N lgN. 18
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 = (n2 + n)/2 = O(n2). ph c t p tr ng h p x u nh t c a Quicksort là O(n2). 19
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 CN = (N+1) + (1/N) (Ck-1 + CN-k) 1 v iN 2 và C1 = C0 = 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. 20