Chương 2: Phân tích độ phức tạp của một số gải thuật sắp thứ tự và tìm kiếm

Chia sẻ: Ba Xoáy | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

63
lượt xem 5
download

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

Xét những phương pháp sắp thứ tự một tập tin gồm các mẫu tin có chứa khóa. Khóa mà là một phần của mẫu tin, được dùng để điều khiển việc sắp thứ tự. Mục tiêu: Sắp xếp các mẫu tin sao cho các trị khóa của chúng có thứ tự theo một qui luật thứ tự nào đó.

Chủ đề:

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

Lưu

Nội dung Text: Chương 2: Phân tích độ phức tạp của một số gải thuật sắp thứ tự và tìm kiếm

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 c g i là s p th t n i chính thì gi i thu t s p th t (internal sorting). c g i là s p th Vi c s p th t t p tin l u b nh ph 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 .”  45 45 45 45 390  182 182 182 205 205  205 205 182 182 205  235 45 390 390 390 390 235 235 235 235 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 390 205 182 182 205 390 205 205 182 182 390 235 45 45 45 390 235 235 235 235 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 c g i là ph n t ch t - pivot). nó ( Ph n t này 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. v trí k có cùng xác Ph n còn l i là do s ki n m i ph n t 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