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

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ự.
Nội dung trích xuất từ tài liệu:
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 Qui ...