Chương 4: Kỹ thuật phân tích giải thuật

Chia sẻ: Lê Minh Thông | Ngày: | Loại File: PDF | Số trang:83

0
222
lượt xem
131
download

Chương 4: Kỹ thuật phân tích giải thuật

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

Trong chương này chúng ta sẽ nghiên cứu các vấn đề sau: Sự cần thiết phải phân tích các giải thuật; Thời gian thực hiện của chương trình; Tỷ suất tăng và độ phức tạp của giải thuật; Tính thời gian thực hiện của chương trình; Phân tích các chương trình đệ quy

Chủ đề:
Lưu

Nội dung Text: Chương 4: Kỹ thuật phân tích giải thuật

  1. Collected by The_Wall (11/10/2005) 1. M c tiêu 2. Ki n th c c b n c n có h c ch ng này 3. Tài li u tham kh o có liên quan n ch ng 4. N i dung: I.1 - S c n thi t ph i phân tích gi i thu t. I.2 - Th i gian th c hi n c a gi i thu t. I.3 - T su t t ng và ph c t p c a gi i thu t. I.4 - Cách tính ph c t p. I.5 - Phân tích các ch ng trình quy. 5. V n nghiên c u c a trang k ti p Trong ch ng này chúng ta s nghiên c u các v n sau: · S c n thi t ph i phân tích các gi i thu t. · Th i gian th c hi n c a ch ng trình. · T su t t ng và ph c t p c a gi i thu t. · Tính th i gian th c hi n c a ch ng trình. · Phân tích các ch ng trình quy. I.1- S C N THI T PH I PHÂN TÍCH GI I THU T Trong khi gi i m t bài toán chúng ta có th có m t s gi i thu t khác nhau, v n là c n ph i ánh giá các gi i thu t ó l a ch n m t gi i thu t t t (nh t). Thông th ng thì ta s c n c vào các tiêu chu n sau: 1.- Gi i thu t úng n. 2.- Gi i thu t n gi n. 3.- Gi i thu t th c hi n nhanh. V i yêu c u (1), ki m tra tính úng n c a gi i thu t chúng ta có th cài t gi i thu t ó và cho th c hi n trên máy v i m t s b d li u m u r i l y k t qu thu c so sánh v i k t qu ã bi t. Th c ra thì cách làm này không ch c ch n b i vì có th gi i thu t úng v i t t c các b d li u chúng ta ã th nh ng l i sai v i m t b d li u nào ó. V l i cách làm này ch phát hi n ra gi i thu t sai ch ch a ch ng minh c là nó úng. Tính úng n c a gi i thu t c n ph i c ch ng minh ng toán h c. T t nhiên u này không n gi n và do v y chúng ta s không c p n ây. Khi chúng ta vi t m t ch ng trình s d ng m t vài l n thì yêu c u (2) là quan tr ng nh t. Chúng ta c n m t gi i thu t d vi t ch ng trình nhanh chóng có c k t q a , th i gian th c hi n ch ng trình không c cao vì dù sao thì ch ng trình ó c ng ch s d ng m t vài l n mà thôi. Tuy nhiên khi m t ch ng trình c s d ng nhi u l n thì thì yêu c u ti ït ki m th i gian Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 1
  2. Collected by The_Wall (11/10/2005) th c hi n ch ng trình l i r t quan tr ng c bi t i v i nh ng ch ng trình mà khi th c hi n c n d li u nh p l n do ó yêu c u (3) s c xem xét m t cách k càng. Ta g i nó là hi u qu th i gian th c hi n c a gi i thu t. I.2- TH I GIAN TH C HI N C A GI I THU T I.2.1- Th i gian th c hi n ch ng trình. I.2.2- n v o th i gian th c hi n. I.2.3- Th i gian th c hi n trong tr ng h p x u nh t. M t ph ng pháp xác nh hi u qu th i gian th c hi n c a m t gi i thu t là l p trình nó và o ng th i gian th c hi n c a ho t ng trên m t máy tính xác nh i v i t p h p c ch n l c các li u vào. Th i gian th c hi n không ch ph thu c vào gi i thu t mà còn ph thu c váo t p các ch th a máy tính, ch t l ng c a máy tính và k x o c a ng i l p trình. S thi hành c ng có th u ch nh th c hi n t t trên t p c bi t các d li u vào c ch n. v t qua các tr ng i này, các nhà khoa h c máy tính ã ch p nh n tính ph c t p c a th i gian c ti p c n nh m t s o l ng c n s th c thi c a gi i thu t. Thu t ng tính hi u qu s c p n s o l ng này và c bi t i i s ph c t p th i gian trong tr ng h p x u nh t. I.2.1- Th i gian th c hi n ch ng trình. Th i gian th c hi n m t ch ng trình là m t hàm c a kích th c d li u vào, ký hi u T(n) trong ó n là kích th c ( l n) c a d li u vào. Ví d 1-1: Ch ng trình tính t ng c a n s có th i gian th c hi n là T(n) = cn trong ó c là t h ng s . Th i gian th c hi n ch ng trình là m t hàm không âm, t c là T(n) ≥0 ∀n≥0. I.2.2- n v o th i gian th c hi n. n v c a T(n) không ph i là n v o th i gian bình th ng nh gi , phút giây... mà th ng c xác nh b i s các l nh c th c hi n trong m t máy tính lý t ng. Ví d 1-2: Khi ta nói th i gian th c hi n c a m t ch ng trình là T(n) = cn thì có ngh a là ch ng trình y c n cn ch th th c thi. I.2.3- Th i gian th c hi n trong tr ng h p x u nh t. Nói chung thì th i gian th c hi n ch ng trình không ch ph thu c vào kích th c mà còn ph thu c vào tính ch t c a d li u vào. Ngh a là d li u vào có cùng kích th c nh ng th i gian th c hi n ch ng trình có th khác nhau. Ch ng h n ch ng trình s p x p dãy s nguyên t ng d n, khi ta cho vào dãy có th t thì th i gian th c hi n khác v i khi ta cho vào dãy ch a có th t , ho c khi ta cho vào m t dãy ã có th t t ng thì th i gian th c hi n c ng khác so v i khi ta cho vào m t dãy ã có th t gi m. Vì v y th ng ta coi T(n) là th i gian th c hi n ch ng trình trong tr ng h p x u nh t trên li u vào có kích th óc n, t c là: T(n) là th i gian l n nh t th c hi n ch ng trình i v i m i d li u vào có cùng kích th c n. I.3- T SU T T NG VÀ PH C T P C A GI I THU T Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 2
  3. Collected by The_Wall (11/10/2005) I.3.1- T su t t ng I.3.2- Khái ni m ph c t p c a gi i thu t I.3.1- T su t t ng Ta nói r ng hàm không âm T(n) có su t t ng (growth rate) f(n) n u t n t i các h ng s c và n0 sao cho T(n) f(n) v i m i n n0. Ta có th ch ng minh c r ng “Cho m t hàm không âm T(n) b t k , ta luôn tìm ct su t t ng f(n) c a nó”. Ví d 1-3: Gi s T(0) = 1, T(1) = 4 và t ng quát T(n) = (n+1)2. t n0 = 1 và c = 4 thì v i m i n 1 chúng ta d dàng ch ng minh r ng T(n) = (n+1)2 4n2 v i m i n 1, t c là t su t t ng c a T(n) là n2. Ví d 1-4: T su t t ng c a hàm T(n) = 3n3 + 2n2 là n3. Th c v y, cho n0 = 0 và c = 5 ta d dàng ch ng minh r ng v i m i n 0 thì 3n3 + 2n2 5n3 I.3.2- Khái ni m ph c t p c a gi i thu t Gi s ta có hai gi i thu t P1 và P2 v i th i gian th c hi n t ng ng là T1(n) = 100n2 (v i t su t t ng là n2) và T2(n) = 5n3 (v i t su t t ng là n3). Gi i thu t nào s th c hi n nhanh h n? Câu tr i ph thu c vào kích th c d li u vào. V i n < 20 thì P2 s nhanh h n P1 (T2
  4. Collected by The_Wall (11/10/2005) I.4.3- Qui t c t ng quát phân tích m t ch ng trình I.4.4- ph c t p c a ch ng trình có g i ch ng trình con không qui Cách tính ph c t p c a m t gi i thu t b t k là m t v n không n gi n. Tuy nhiên ta có th tuân theo m t s nguyên t c sau: I.4.1- Qui t c c ng: N u T1(n) và T2(n) là th i gian th c hi n c a hai n ch ng trình P1 và P2; và T1(n)=O(f(n)), T2(n)=O(g(n) thì th i gian th c hi n c a n hai ch ng trình ó i ti p nhau là T(n)=O(max(f(n),g(n))) Ví d 1-6: L nh gán x:=15 t n m t h ng th i gian hay O(1) L nh c d li u READ(x) t n m t h ng th i gian hay O(1) V y th i gian th c hi n c hai l nh trên n i ti p nhau là O(max(1,1))=O(1) I.4.2- Qui t c nhân: N u T1(n) và T2(n) là th i gian th c hi n c a hai n ch ng trình P1và P2 và T1(n) = O(f(n)), T2(n) = O(g(n) thì th i gian th c hi n c a n hai n ch ng trình ó ng nhau là T(n) = O(f(n).g(n)) I.4.3- Qui t c t ng quát phân tích m t ch ng trình: - Th i gian th c hi n c a m i l nh gán, READ, WRITE là O(1) - Th i gian th c hi n c a m t chu i tu n t các l nh c xác nh b ng qui t c c ng. Nh y th i gian này là th i gian thi hành m t l nh nào ó lâu nh t trong chu i l nh. - Th i gian th c hi n c u trúc IF là th i gian l n nh t th c hi n l nh sau THEN ho c sau ELSE và th i gian ki m tra u ki n. Th ng th i gian ki m tra u ki n là O(1). - Th i gian th c hi n vòng l p là t ng (trên t t c các l n l p) th i gian th c hi n thân vòng p. N u th i gian th c hi n than vòng l p không i thì th i gian th c hi n vòng l p là tích c a s l n p v i th i gian th c hi n thân vòng l p. Ví d 1-7: Tính th i gian th c hi n c a n ch ng trình procedure Bubble (var a: array[1..n] of integer); var i,j,temp: integer; begin {1} for i:=1 to n-1 do {2} for j:=n downto i+1 do {3} if a[j-1]>a[j] then begin { i ch a[i], a[j] } {4} temp:=a[j-1]; {5} a[j-1]:=a[j]; {6} a[j]:=temp; end; end; Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 4
  5. Collected by The_Wall (11/10/2005) C ba l nh i ch {4} {5} {6} t n O(1) th i gian, do ó l nh {3} t n O(1). Vòng l p {2} th c hi n (n-i) l n, m i l n O(1) do ó vòng l p {2} t n O((n-i).1)=O(n-i). Vòng l p {1} l p (n-1) l n v y ph c t p c a gi i thu t là: I.4.4- ph c t p c a ch ng trình có g i ch ng trình con không qui N u chúng ta có m t ch ng trình v i các ch ng trình con không quy, tính th i gian th c hi n c a ch ng trình, tr c h t chúng ta tính th i gian th c hi n c a các ch ng trình con không i các ch ng trình con khác. Sau ó chúng ta tính th i gian th c hi n c a các ch ng trình con ch i các ch ng trình con mà th i gian th c hi n c a chúng ã c tính. Chúng ta ti p t c quá trình ánh giá th i gian th c hi n c a m i ch ng trình con sau khi th i gian th c hi n c a t t c các ch ng trình con mà nó g i ã c ánh giá. Cu i cùng ta tính th i gian cho ch ng trình chính. Gi s ta cô m t h th ng các ch ng trình g i theo s sau: Ch ng trình A g i hai ch ng trình con là B và C, ch ng trình B g i hai ch ng trình con là B1 và B2, ch ng trình B1 g i hai ch ng trình con là B11 và B12. tính th i gian th c hi n c a A, ta tính theo các b c sau: - Tính th i gian th c hi n c a C, B2, B11 và B12. - Tính th i gian th c hi n c a B1. - Tính th i gian th c hi n c a B. - Tính th i gian th c hi n c a A. Ví d 1-8: Ta có th vi t l i ch ng trình s p x p bubble nh sau: procedure Swap (var x, y: integer); var temp: integer; begin temp := x; x := y; y := temp; end; Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 5
  6. Collected by The_Wall (11/10/2005) procedure Bubble (var a: array[1..n] of integer); var i,j :integer; begin {1} for i:=1 to n-1 do {2} for j:=n downto i+1 do {3} if a[j-1]>a[j] then Swap(a[j-1], a[j]); end; Trong cách vi t trên, ch ng trình Bubble g i ch ng trình con Swap, do ó tính th i gian th c hi n c a Bubble, tr c h t ta c n tính th i gian th c hi n c a Swap. D th y th i gian th c hi n a Swap là O(1) vì nó ch bao g m 3 l nh gán. Trong Bubble, l nh {3} g i Swap nên ch t n O(1), l nh {2} th c hi n n-i l n, m i l n t n O(1) nên t n O(n-i). L nh {1} th c hi n n-1 l n nên I.5- PHÂN TÍCH CÁC CH NG TRÌNH QUY I.5.1- Thành l p ph ng trình quy I.5.2- Gi i ph ng trình quy V i các ch ng trình có g i các ch ng trình con quy, ta không th áp d ng cách tính nh a trình bày trong m c I.4.4 b i vì m t ch ng trình quy s g i chính b n thân nó. V i các ch ng trình quy, tr c h t ta c n thành l p các ph ng trình quy, sau ó gi i ph ng trình quy, nghi m c a ph ng trình quy s là th i gian th c hi n c a ch ng trình quy. I.5.1- Thành l p ph ng trình quy Ph ng trình quy là m t ph ng trình bi u di n m i liên h gi a T(n) và T(k), trong ó T(n) là th i gian th c hi n ch ng trình v i kích th c d li u nh p là n, T(k) th i gian th c hi n ch ng trình v i kích th c d li u nh p là k, v i k < n. thành l p c ph ng trình quy, ta ph i c n c vào ch ng trình quy. Ví d 1-9: Xét hàm tính giai th a vi t b ng gi i thu t quy nh sau: function Giai_thua(n:integer): integer; begin if n=0 then Giai_thua :=1 else Giai_thua := n* Giai_thua(n-1); end; i T(n) là th i gian th c hi n vi c tính n giai th a, thì T(n-1) là th i gian th c hi n vi c tính n-1 giai th a. Trong tr ng h p n=0 thì ch ng trình ch th c hi n m t l nh gán Giai_thua:=1, nên t n O(1), do ó ta có T(0) = C1. Trong tr ng h p n>0 ch ng trình ph i g i quy Giai_thua(n-1), vi c i quy này t n T(n-1), sau khi có k t qu c a vi c g i quy, ch ng trình ph i nhân k t qu ó i n và gán cho Giai_thua. Th i gian th c hi n phép nhân và phép gán là m t h ng C2. V y ta có Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 6
  7. Collected by The_Wall (11/10/2005) ây là ph ng trình quy tính th i gian th c hi n c a ch ng trình quy Giai_thua. Ví d 1-10: Chúng ta xét th t c MergeSort m t cách phác th o nh sau: function MergeSort (L:List ; n:integer) : List; var L1,L2 : List; begin if n = 1 then return(L) else begin Chia L thành 2 n a L1 và L2 , m i m t n a có dài n/2; return(Merge(MergeSort (L1 , n/2), MergeSort(L2, n/2))); end; end; Ch ng h n s p x p danh sách L g m 8 ph n t 7, 4, 8, 9, 3, 1, 6, 2 ta có mô hình minh h a a MergeSort nh sau: Hàm MergeSort nh n m t danh sách có dài n và tr v m t danh sách ã c s p x p. Th c Merge nh n hai danh sách ã c s p L1 và L2 m i danh sách có dài n/2, tr n chúng l i v i nhau c m t danh sách g m n ph n t có th t . Gi i thu t chi ti t c a Merge ta s bàn sau, chúng ta ch ý r ng th i gian Merge các danh sách có dài n/2 là O(n). Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 7
  8. Collected by The_Wall (11/10/2005) G i T(n) là th i gian th c hi n MergeSort m t danh sách n ph n t thì T(n/2) là th i gian th c hi n MergeSort m t danh sách n/2 ph n t , ta có th vi t ph ng trình quy nh sau: Trong ó c1 là th i gian ph i t n khi L có dài 1. Trong tr ng h p n > 1, th i gian c a MergeSort c chia làm hai ph n. Ph n g i quy MergeSort m t danh sách có dài n/2 là T(n/2) do ó ta có 2T(n/2). Ph n th hai bao g m phép th n >1, chia danh sách L thành hai n a b ng nhau và Merge. Ba thao tác này l y th i gian không i i v i phép th ho c t l v i n i v i ng t và Merge. Nh v y h ng c2 c ch n và c2n là th i gian t ng làm các vi c ó ngo i tr g i quy. I.5.2- Gi i ph ng trình quy Có ba ph ng pháp gi i ph ng trình quy: 1.- Ph ng pháp truy h i 2.- Ph ng pháp oán nghi m. 3.- L i gi i t ng quát c a m t l p các ph ng trình quy. Ph ng pháp truy h i Dùng quy thay th b t k T(m) v i m < n vào phía ph i c a ph ng trình cho n khi t t T(m) v i m > 1 c thay th b i bi u th c c a các T(1). Vì T(1) luôn là h ng nên chúng ta có công th c c a T(n) ch a các s h ng ch liên quan n n và các h ng s . Gi i ph ng trình. Ví d 1-10: Gi i ph ng trình: Ta có: Gi s n = 2k, quá trình suy r ng s k t thúc khi i =k, khi ó ta có: T(n) = 2kT(1) + kC2n Vì 2k = n nên k = logn và v i T(1) =C1 nên ta có Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 8
  9. Collected by The_Wall (11/10/2005) T(n) = C1n + C2nlogn Hay T(n) là O(nlogn). oán nghi m Ta oán m t nghi m f(n) và dùng ch ng minh quy n p ch ng t r ng T(n) f(n) v i m i n. Thông th ng f(n) là m t trong các hàm quen thu c nh logn, n, nlogn, n2, n3, 2n, n!, nn. ôi khi chúng ta ch oán d ng c a f(n) trong ó có m t vài tham s ch a xác nh (ch ng h n 2 f(n) = an v i a ch a xác nh) và trong quá trình ch ng minh quy n p ta s suy di n ra giá tr thích p c a các tham s . Ví d 1-11: Gi i ph ng trình quy Gi s chúng ta oán f(n) = anlogn. V i n = 1 ta th y r ng cách oán nh v y không cb i vì anlog n có giá tr 0 không ph thu c vào giá tr c a a. Vì th ta th ti p theo f(n) = anlogn + b. V i n = 1 ta có, T(1) = C1 và f(1) = b, mu n T(1) f(1) thì b C1 (*) Gi s r ng T(k) aklogk + b v i m i k < n (I.2).Ta s ch ng minh T(n) anlogn + b Gi s n 2, t (I.1) ta có T(n) = 2T(n/2) + C2n Áp d ng (I.2) v i k = n/2 < n ta có: T(n) = 2T(n/2) + C2n 2[an/2log(n/2) + b] + C2n T(n) anlogn - an + 2b + C2n T(n) (anlogn + b) + [b + (C2 - a)n] . N u l y a C2 + b (**) ta c T(n) (anlogn + b) + [b +(C2 - C2 - b )n ] T(n) (anlogn + b) + (1-n) b T(n) an logn + b. N u ta l y a và b sao cho c (*) và (**) u tho mãn thì T(n) an logn + b v i m i n. D dàng ta có b = C1 và a= C1 +C2 ta c T(n) (C1 + C2)nlogn + C1 v i m i n. Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................ Trang 9
  10. Collected by The_Wall (11/10/2005) Hay nói cách khác T(n) là O(nlogn). i gi i t ng quát cho m t l p các ph ng trình quy gi i bài toán kích th c n, ta chia bài toán ã cho thành a bài toán con, m i bài tóan con có kích th c n/b. Gi i các bài toán con này và t ng h p k t qu l i c k t qu c a bài toán ã cho. i các bài toán con chúng ta c ng làm nh v y. K thu t này s d n chúng ta n m t ch ng trình quy. Gi thi t r ng m i bài toán con kích th c 1 l y m t n v th i gian và th i gian chia bài toán kích th c n thành các bài toán con kích th c n/b và t ng h p k t qu t các bài toán con c l i gi i c a bài toán ban u là d(n). (Ch ng h n i v i thí d MergeSort, chúng ta có a = b = 2, và d(n) = C2n/C1. Xem C1 là m t n v ). G i T(n) là th i gian gi i bài toán kích th c n thì ta có ph ng trình quy: Ta s d ng ph ng pháp truy h i gi i ph ng trình này Gi s n = bk ta c: T(n/bk) = T(1) = 1. Thay vào trên v i i = k ta có: Hàm ti n tri n, nghi m thu n nh t và nghi m riêng Trong ph ng trình quy (I.1) hàm th i gian d(n) c g i là hàm ti n tri n (driving function) Trong công th c (I.2), ak = nlogba c g i là nghi m thu n nh t (homogeneous solutions). Nghi m thu n nh t là nghi m chính xác khi d(n) = 0 v i m i n. Nói m t cách khác, nghi m thu n nh t bi u di n th i gian gi i t t c các bài toán con. Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 10
  11. Collected by The_Wall (11/10/2005) Trong công th c (I.2), c g i là nghi m riêng (particular solutions). Nghi m riêng bi u di n th i gian ph i tr t o ra các bài toán con và t ng h p các k t qu a chúng. Nhìn vào công th c ta th y nghi m riêng ph thu c vào hàm ti n tri n, s l ng và kích th c các bài toán con. Khi tìm nghi m c a ph ng trình (I,1), chúng ta ph i tìm nghi m riêng và so sánh v i nghi m thu n nh t. N u nghi m nào l n h n, ta l y nghi m ó làm nghi m c a ph ng trình (I,1). Vi c xác nh nghi m riêng không n gi n chút nào, tuy v y, chúng ta c ng tìm cm tl p các hàm ti n tri n có th d dàng xác nh nghi m riêng. Hàm nhân M t hàm f(n) c g i là hàm nhân (multiplicative function) n u f(m.n) = f(m).f(n) v i m i nguyên d ng m và n. Ví d 1-12: Hàm f(n) = nk là m t hàm nhân, vì f(m.n) = (m.n)k = mk.nk = f(m) f(n) u d(n) trong (I.1) là m t hàm nhân thì theo tính ch t c a hàm nhân ta có d(bk-j) = (d(b))k-j và nghi m riêng c a (I.2) là: Xét ba tr ng h p sau: 1.- N u a > d(b) thì nghi m riêng là O(ak) = O(nlogba). Nh v y nghi m riêng và nghi m thu n nh t b ng nhau do ó T(n) là O(nlogba). Ta c ng th y th i gian th c hi n ch ph thu c vào a, b mà không ph thu c vào hàm ti n tri n d(n). Vì v y c i ti n gi i thu t ta c n gi m a ho c t ng b. 2.- N u a < d(b) thì nghi m riêng là O(d(b)k) = O(nlogbd(b)). Trong tr ng h p này nghi m riêng n h n nghi m thu n nh t nên T(n) = O(nlogbd(b)). c i ti n gi i thu t chúng ta c n ý n c d(n), a và b cùng m c nh nhau. Tr ng h p c bi t quan tr ng khi d(n) = n . Khi ó d(b) = b và logb(b ) = . Vì th nghi m riêng là O(n ) và do v y T(n) là O(n ). 3.- N u a = d(b) thì công th c (I.5) không xác inh nên ta tính tr c ti p nghi m riêng: Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 11
  12. Collected by The_Wall (11/10/2005) Vì a= d(b) nên nghi m riêng là nlogbalogbn và nghi m này l n g p logbn l n nghi m thu n nh t. Do ó T(n) = O(nlogbalogbn). Trong tr ng h p c bi t d(n) = n ta c T(n) = O(n logn). Chú ý khi gi i m t ph ng trình quy c th , ta ph i xem ph ng trình ó có thu c d ng ph ng trình t ng quát hay không. N u có thì ph i xét xem hàm ti n tri n có ph i là hàm nhân không. u có thì ta xác nh a, d(b) và d a vào s so sánh gi a a và d(b) mà v n d ng m t trong ba tr ng p nói trên. Ví d 1-13: Gi i các ph ng trình quy sau v i T(1) = 1 và 1/- T(n) = 4T(n/2) + n 2/- T(n) = 4T(n/2) + n2 3/- T(n) = 4T(n/2) + n3 Trong m i tr ng h p, a=4, b=2 và nghi m thu n nh t là n2. V i d(n) = n ta có d(b) = 2 vì a = 4 > d(b) nên nghi m riêng c ng là n2 và T(n) = O(n2) trong ph ng trình (1). Trong ph ng trình (3), d(n) = n3, d(b) = 8 và a < d(b). Vì v y nghi m riêng là O(nlogbd(b)) = O(n ) và T(n) c a (3) là O(n3). 3 Trong ph ng trình (2) chúng ta có d(b) = 4 = a nên T(n) = O(n2logn). Các hàm ti n tri n khác Ta xét hai tr ng h p d i d ng hai ví d , tr ng h p 1 là t ng quát hóa c a hàm b t k là tích a m t hàm nhân v i m t h ng l n h n ho c b ng 1. Tr ng h p th hai là hàm ti n tri n không ph i là m t hàm nhân. Ví d 1-14: Gi i pg ng trình quy sau : T(1) = 1 T(n) = 3T(n/2) + 2n1.5 ây, 2n1.5 không ph i là hàm nhân nh ng n1.5 là hàm nhân. t U(n) = T(n)/2 v i m i n thì U(1) = 1/2 U(n) = 3U(n/2) + n1.5 Nghi m thu n nh t khi U(1) = 1 là nlog3 = n1.59; vì U(1) = 1/2 nên nghi m thu n nh t là n1.59/2 là 1.59 O(n ). Vì a = 3 và b = 2 và b1.5 = 2.82 < a, nghi m riêng c ng là O(n1.59) và do ó U(n) = O(n1.59) . Vì Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 12
  13. Collected by The_Wall (11/10/2005) T(n) = 2U(n) nên T(n) = O(n1.59) hay T(n) = O(nlog3). Ví d 1-15: Gi i ph ng trình quy sau : T(1) = 1 T(n) = 2T(n/2) + nlogn Vì a = b = 2 nên nghi m thu n nh t là n. Tuy nhiên, d(n) = nlogn không ph i là hàm nhân ta ph i tính nghi m riêng b ng cách xét tr c ti p: Vì k = logn chúng ta có nghi m riêng là O(nlog2n), nghi m này l n h n nghi m thu n nh t và T(n) = O(nlog2n). Bài 1: Tính th i gian th c hi n c a các n ch ng trình sau: a) Tính t ng c a các s Sum := 0; for i:=1 to n do begin readln(x); Sum := Sum + x; end; b) Tính tích hai ma tr n vuông c p n C = A*B: for i := 1 to n do for j := 1 to n do begin c[i,j] := 0; for k := 1 to n do c[i,j] := c[i,j] + a[i,k] * b[k,j]; end; Bài 2: Gi i các ph ng trình quy sau v i T(1) = 1 và a) T(n) = 3T(n/2) + n b) T(n) = 3T(n/2) + n2 c) T(n) = 8T(n/2) + n3 Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 13
  14. Collected by The_Wall (11/10/2005) Bài 3: Gi i các ph ng trình quy sau v i T(1) = 1 và a) T(n) = 4T(n/3) + n b) T(n) = 4T(n/3) + n2 c) T(n) = 9T(n/3) + n2 Bài 4: Gi i các ph ng trình quy sau v i T(1) = 1 và a) T(n) = T(n/2) + 1 b) T(n) = 2T(n/2) + logn c) T(n) = 2T(n/2) + n d) T(n) = 2T(n/2) + n2 Bài 5: Gi i các ph ng trình quy sau b ng ph ng pháp oán nghi m: a) T(1) = 2 và T(n) = 2T(n-1) + 1 v i ∀ n 2 b) T(1) = 1 và T(n) = 2T(n-1) + n v i ∀ n 2 Bài 6: Cho m t m ng n s nguyên c s p th t t ng. Vi t hàm tìm m t s nguyên trong ng ó, n u tìm th y thì tr v TRUE, ng c l i tr v FALSE. d ng hai ph ng pháp tìm ki m tu n t và tìm ki m nh phân. V i m i ph ng pháp hãy vi t m t hàm tìm và tính th i gian th c hi n c a hàm ó. Bài 7: Tính th i gian th c hi n c a gi i thu t quy gi i bài toán Tháp Hà n i v i n t ng? Bài 8: Xét nh ngh a s t h p ch p k c a n nh sau: a) Vi t m t hàm quy tính s t h p ch p k c a n. Tính th i gian th c hi n c a gi i thu t nói trên. Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 14
  15. Collected by The_Wall (11/10/2005) 1. M c tiêu 2. Ki n th c c b n c n có h c ch ng này 3. Tài li u tham kh o có liên quan n ch ng 4. N i dung: II.1 - Bài toán s p x p. II.2 - Các ph ng pháp s p x p n gi n II.3 - Quicksort. II.4 - Heapsort. II.5 - Binsort. 5. V n nghiên c u c a trang k ti p Trong ch ng này chúng ta s nghiên c u các v n sau: · Bài toán s p x p. · M t s gi i thu t s p x p n gi n. · QuickSort · HeapSort · BinSort II.1- BÀI TOÁN S P X P II.1.1 T m quan tr ng c a bài toán s p x p II.1.2 S p x p trong và s p x p ngoài II.1.3 T ch c d li u và ngôn ng cài t II.1.1 T m quan tr ng c a bài toán s p x p S p x p m t danh sách các i t ng theo m t th t nào là m t bài toán th ng cv n ng trong các ng d ng tin h c. Ví d ta c n s p x p danh sách thí sinh theo tên v i th t Alphabet, ho c s p x p danh sách sinh viên theo m trung bình v i th t t cao n th p. M t ví d khác là khi c n tìm ki m m t i t ng trong m t danh sách các i t ng b ng gi i thu t tìm ki m nh phân thì danh sách các i t ng này ph i c s p x p tr c ó. Tóm l i s p x p là m t yêu c u không th thi u trong khi thi t k các ph n m m. II.1.2 S p x p trong và s p x p ngoài S p x p trong là s s p x p d li u c t ch c trong b nh trong cu máy tính, ó ta có th s d ng kh n ng truy nh p ng u nhiên c a b nh và do v y s th c hi n r t nhanh. S p x p ngoài là s s p x p c s d ng khi s l ng i t ng c s p x p l n không th u tr trong b nh trong mà ph i l u tr î trên b nh ngoài. C th là ta s s p x p d li u cl u tr trong các t p tin. Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 15
  16. Collected by The_Wall (11/10/2005) Ch ng này t p trung gi i quy t v n s p x p trong còn s p x p ngoài s c nghiên c u trong ch ng IV. II.1.3 T ch c d li u và ngôn ng cài t Các i t ng c n c s p x p là các m u tin g m m t ho c nhi u tr ng. M t trong các tr ng c g i là khóa (key), ki u c a nó là m t ki u có quan h th t (nh các ki u s nguyên, s th c, chu i ký t ...). Danh sách các i t ng c n s p x p s là m t m ng c a các m u tin v a nói trên. M c ích a vi c s p x p là t ch c l i các m u tin sao cho các khóa c a chúng c s p th t t ng ng v i quy lu t s p x p. trình bày các ví d minh h a chúng ta s dùng PASCAL làm ngôn ng th hi n và s d ng khai báo sau: const N = 100; type KeyType = integer; OtherType = real; RecordType = Record Key : KeyType; OtherFields : OtherType; end; var a : array[1..N] of RecordType; procedure Swap(var x,y:RecordType); var temp : RecordType; begin temp := x; x := y; y := temp; end; n th y r ng th t c Swap l y O(1) th i gian vì ch th c hi n 3 l nh gán n i ti p nhau. II.2- CÁC PH NG PHÁP S P X P N GI N II.2.1- S p x p ch n II.2.2- S p x p xen II.2.3- S p x p n i b t Các gi i thu t n gi n th ng l y O(n2) th i gian s px pn it ng và các gi i thu t này th ng ch dùng s p các danh sách có ít i t ng. V i m i gi i thu t chúng ta s nghiên c u các ph n: gi i thu t, ví d , ch ng trình và phân tích ánh giá. Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 16
  17. Collected by The_Wall (11/10/2005) II.2.1- S p x p ch n (Selection Sort) Gi i thu t ây là ph ng pháp s p x p n gi n nh t c ti n hành nh sau: · u tiên ch n ph n t có khóa nh nh t trong n ph n t t a[1] n a[n] và hoán v nó i ph n t a[1]. · Ch n ph n t có khóa nh nh t trong n-1ph n t t a[2] n a[n] và hoán v nó v i a[2]. · T ng quát b c th i, ch n ph n t có khoá nh nh t trong n-i+1 ph n t t a[i] n a[n] và hoán v nó v i a[i]. · Sau n-1 b c này thì m ng ã c s p x p. Ph ng pháp này c g i là ph ng pháp ch n b i vì nó l p l i quá trình ch n ph n t nh nh t trong s các ph n t ch a c s p. Ví d 2-1: S p x p m ng g m 10 m u tin có khóa là các s nguyên: 5, 6, 2, 2, 10, 12, 9, 10, 9 và 3 Khoá a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] c Ban u 5 6 2 2 10 12 9 10 9 3 c1 2 6 5 2 10 12 9 10 9 3 c2 2 5 6 10 12 9 10 9 3 c3 3 6 10 12 9 10 9 5 c4 5 10 12 9 10 9 6 c5 6 12 9 10 9 10 c6 9 12 10 9 10 c7 9 10 12 10 c8 10 12 10 c9 10 12 t qu 2 2 3 5 6 9 9 10 10 12 Hình 2-1: S p x p ch n Ch ng trình: procedure SelectionSort; var i,j,LowIndex: integer; LowKey: KeyType; begin (1) for i := 1 to n-1 do begin (2) LowIndex := i; (3) LowKey := a[i].key; (4) for j := i+1 to n do (5) if a[j].key < LowKey then Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 17
  18. Collected by The_Wall (11/10/2005) begin (6) LowKey := a[j].key; (7) LowIndex := j; end; (8) Swap(a[i] , a[LowIndex]); end; end; ánh giá: Ph ng pháp s p x p ch n l y O(n2) s p x p n ph n t . Tr c h t ta có th t c Swap l y m t h ng th i gian nh ã nói m c II.1.3. Các l nh (2), (3) u l y O(1) th i gian. Vòng l p for (4) - (7) th c hi n n-i l n, vì j ch y t i+1 n n, m i l n l y O(1), nên l y O(n-i) th i gian. Do ó th i gian t ng c ng là: II.2.2- S p x p xen (Insertion Sort) Gi i thu t Tr c h t ta xem ph n t a[1] là m t dãy ã có th t . ·B c 1, xen ph n t a[2] vào danh sách ã có th t a[1] sao cho a[1], a[2] là m t danh sách có th t . · B c 2, xen ph n t a[3] vào danh sách ã có th t a[1], a[2] sao cho a[1], a[2], a[3] là t danh sách có th t . · T ng quát, b c i, xen ph n t a[i+1] vào danh sách ã có th t a[1],a[2],..a[i] sao cho a[1], a[2],.. a[i+1] là m t danh sách có th t . · Ph n t ang xét a[j] s c xen vào v trí thích h p trong danh sách các ph n t ã c s p tr c ó a[1],a[2],..a[j-1] b ng cách so sánh khoá c a a[j] v i khoá c a a[j-1] ng ngay tr c nó. N u khoá c a a[j] nh h n khoá c a a[j-1] thì hoán i a[j-1] và a[j] cho nhau và ti p t c so sánh khoá c a a[j-1] (lúc này a[j-1] ch a n i dung c a a[j]) v i khoá c a a[j-2] ng ngay tr c nó... Ví d 2-2: S p x p m ng g m 10 m u tin ã cho trong ví d 2-1. Khoá a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] c Ban u 5 6 2 2 10 12 9 10 9 3 c1 5 6 c2 2 5 6 c3 2 2 5 6 c4 2 2 5 6 10 c5 2 2 5 6 10 12 Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 18
  19. Collected by The_Wall (11/10/2005) c6 2 2 5 6 9 10 12 c7 2 2 5 6 9 10 10 12 c8 2 2 5 6 9 9 10 10 12 c9 2 2 3 5 6 9 9 10 10 12 Hình 2-2: S p x p xen Ch ng trình procedure InsertionSort; var i,j: integer; begin {1} for i := 2 to n do begin {2} J := i; {3} while (j>1) and (a[j].key < a[j-1].key) do begin {4} swap(a[j], a[j-1]); {5} j := j-1; end; end; end; ánh giá: Ph ng pháp s p x p ch n l y O(n2) s p x p n ph n t . Ta th y các l nh (4) và (5) u l y O(1). Vòng l p (3) ch y nhi u nh t i-1 l n, m i l n t n O(1) nên (3) l y i-1 th i gian. L nh (2) và (3) là hai l nh n i ti p nhau, l nh (2) l y O(1) nên c hai nh này l y i-1. Vòng l p (1) có i ch y t 2 n n nên n u g i T(n) là th i gian s p n ph n t thì ta có II.2.3- S p x p n i b t (Bubble Sort) Gi i thu t Chúng ta t ng t ng r ng các m u tin c l u trong m t m ng d c, qua quá trình s p, m u tin nào có khóa “nh ” s c n i lên trên. Chúng ta duy t tòan m ng, t d i lên trên. N u hai ph n c nh nhau mà không úng th t t c là n u ph n t “nh h n” l i n m d i thì ph i cho nó “n i lên” b ng cách i ch hai ph n t này cho nhau. C th là: · B c 1: Xét các ph n t t a[n] n a[2], v i m i ph n t a[j], so sánh khoá c a nó v i khoá c a ph n t a[j-1] ng ngay tr c nó. N u khoá c a a[j] nh h n khoá c a a[j-1] thì hoán i a[j] và a[j-1] cho nhau. ·B c 2: Xét các ph n t t a[n] n a[3], và làm t ng t nh trên. · T ng quát b c th i, ta s xét các ph n t t a[n] n a[i+1]. Sau n b c ta thu c m ng có th t Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 19
  20. Collected by The_Wall (11/10/2005) Ví d 2-3: S p x p m ng g m 10 m u tin ã cho trong ví d 2-1. Khoá a[1] a[2] a[3] a[4] a[5] a[6] a[7] a[8] a[9] a[10] c Ban u 5 6 2 2 10 12 9 10 9 3 c1 2 5 6 2 3 10 12 9 10 9 c2 2 5 6 3 9 10 12 9 10 c3 3 5 6 9 9 10 12 10 c4 5 6 9 9 10 10 12 c5 6 9 9 10 10 12 c6 9 9 10 10 12 c7 9 10 10 12 c8 10 10 12 c9 10 12 t qu 2 2 3 5 6 9 9 10 10 12 Hình 2-3: S p x p n i b t Ch ng trình procedure BubbleSort; var i,j: integer; begin (1) for i := 1 to n-1 do (2) for j := n downto i+1 do (3) if a[j].key < a[j-1].key then (4) Swap(a[j],a[j-1]); end; ánh giá: Ph ng pháp s p x p n i b t l y O(n2) s p n ph n t . Dòng l nh (3) l y m t h ng th i gian. Vòng l p (2) th c hi n (n-i) b c, m i b c l y O(1) nên l y O(n-i) th i gian. Nh v y i v i toàn b ch ng trình ta có: II.3- QUICKSORT II.3.1- Ý t ng II.3.2- Thi t k gi i thu t II.3.3- Cài t gi i thu t II.3.4- Th i gian th c hi n c a QuickSort Trong ph n này chúng ta s nghiên c u m t gi i thu t s p x p c dùng m t cách ph bi n là Quick Sort do A.R. Hoare phát minh vào n m 1960. Quick Sort c ánh giá t t nh vào s phân tích toán h c và các kh ng nh v kh n ng c a nó. Quick Sort ã c c i ti n tr thành ph ng pháp c ch n trong các ng d ng s p x p th c t khác nhau. Giáo trình môn Phân tích Gi i Thu t – I C C N TH ........................................................................Trang 20

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản