Xem mẫu

  1. Minh H a Cho dãy có 8 ph n t S p x p theo vi trí tăng d n i=1; j=3 L R X=2 1 2 3 5 7 9 10 15 i j L=1 R=3 ðo n c n s px p 71 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  2. Minh H a Cho dãy có 8 ph n t S p x p theo vi trí tăng d n 1 2 3 5 7 9 10 15 Không còn ño n nào c n s p x p ðo n c n s px p 72 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  3. 10 5 7 3 9 2 15 1 ðo n [1- 8] 7 9 5 15 10 ðo n [4- 8] 9 7 15 10 ðo n [5- 8] 9 10 15 ðo n [6- 8] ðo n [6- 7] 9 10 5 7 ðo n [4- 5] ðo n [1- 3] 1 2 3 73 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  4. Gi i thu t: Bư c 1: i=1; Bư c 2: j=N; Trong khi (j>i) th c hi n: N u a[j]N-1: H t dãy, d ng Ngư c l i: L p l i Bư c 2 74 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  5. void QuickSort(int M[], int First, int Last) Cài ð t { int i, j, tam, x; x = M[(First+Last)/2]; i = First; j = Last; do { while (M[i] X) j--; if (i
  6. ðánh giá gi i thu t: + Trư ng h p t t nh t, khi m ng M có th t tăng: S phép gán: Gmin = N-1 S phép so sánh: Smin = N×Log2(N)/2 S phép hoán v : Hmin = 0 + Trư ng h p x u nh t, khi ph n t X ñư c ch n gi a dãy con là giá tr l n nh t: S phép gán: Gmax = N×(N-1)/2 S phép so sánh: Smax = (N-1)×(N-1) S phép hoán v : Hmax = N×(N-1)/2 + Trung bình: S phép gán: Gavg = (N-1)×(N+2)/4 S phép so sánh: Savg = N×[Log2(N)+2N–2]/4 S phép hoán v : Havg = N×(N-1)/4 76 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  7. Chi phí trung bình O(n*log2n) Chi phí cho trư ng h p x u nh t O(n2) Chi phí này ph thu c vào cách ch n ph n t tr c: - N u ch n ñư c ph n t có giá tr trung bình ta s chia thành 2 dãy b ng nhau - N u ch n nh m ph n t nh nh t (hay l n O(n2) nh t) 77 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  8. 2.3 Bài T p 1. Trình bày tư tư ng và minh h a gi i thu t tìm ki m tuy n tính, tìm ki m nh phân 2. Cài ñ t thu t toán tìm tuy n tính b ng cách: - S d ng vòng l p for - S d ng vòng l p while 3. Trong trư ng h p các ph n t c a dãy ñã có th t tăng (ho c gi m) hãy cài ñ t l i thu t toán tìm nh phân 78 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
  9. 1. Trình bày tư tư ng và minh h a 5 gi i thu t s p x p 2. Cài ñ t 5 gi i thu t s p x p theo các trư ng h p và ñi n k t qu s l n th c hi n các phép toán vào b ng sau: 79 This is trial version Khoa CNTT Trư ng Cð CNTT TP.HCM © Dương Thành Ph t-www.thayphet.net www.adultpdf.com
nguon tai.lieu . vn