Bài giảng Thiết Kế và Đánh Giá Thuật Toán - Chặn dưới sắp xếp - Lê Nguyên Khôi

Nội dung text: Bài giảng Thiết Kế và Đánh Giá Thuật Toán - Chặn dưới sắp xếp - Lê Nguyên Khôi

1. Thi ết Kế & Đánh Giá Thu ật Toán Ch ặn Dướ i Sắp Xếp TS. Lê Nguyên Khôi Tr ườ ng Đại Học Công Ngh ệ - ĐHQGHN
2. Nội Dung
   Ch n trên (upper bound - )
   Ch n d i (lower bound - )
   Sp xp trong th i gian tuy n tính
   Sp xp m (Counting sort)
   Sp xp cơ s (Radix sort)
   Sp xp gi (Bucket sort) 1
3. Ch ặn Trên
   Bài toán X: d li u u vào xây dng thu t toán ch y trong th i gian (())
   (): th hi n ph c tp (hay khó) gi i bài toán X
   Mc tiêu: xác nh càng nh càng tt
   Ch n trên () giúp xác nh gi i bài toán X khó c nào 2
4. Ch ặn Dướ i
   Gi i bài toán X, bt c thu t toán nào cng ch y trong th i gian (())
   Mc tiêu: xác nh càng ln càng tt
   Ch n d i () giúp xác nh thu t toán gi i bài toán X ã tt ch a
   Ví d:
   Thu t toán ch y trong th i gian ( log )
   Ch n d i ( log ) gi i bài toán
   Ci ti n thu t toán thu hp kho ng log 3
5. Ch ặn Của Sắp Xếp
   Ch n trên / d i ()
   Ni bt (bubble sort)
   Chèn (insertion sort)
   La ch n (selection sort)
   Ch n trên log / d i ( log )
   Gp (merge sort)
   Cây th t b ph n (heap sort)
   Nhanh (quick sort) – tr ng hp trung bình 4
6. Ch ặn Dướ i Sắp Xếp
   Các thu t toán sp xp va cp:
   u da trên so sánh gi a các ph n t
   Ch n d i ( log )
   Sp xp so sánh (comparison-based sort)
   Không khác bi t v ph c tp
   Khác bi t v th i gian ch y theo mt hng s
   Mt s thu t toán không da trên so sánh gi a các ph n t
   Không áp dng ch n d i ( log ) 5
7. Ch ặn Dướ i Sắp Xếp – Ch ứng Minh
   S dng mô hình Cây Quy t nh
   Cây nh phân
   Nút trong ng vi phép so sánh 2 ph n t
   Nhánh trái ng vi kt qu nh hơn bng
   Nhánh ph i ng vi kt qu ln hơn
   Lá ng vi li gi i (th t các ph n t) 6
8. Cây Quy ết Định Sp xp Nút trong vi th hi n so sánh vi Cây con trái th hi n các b c so sánh nu Cây con ph i th hi n các b c so sánh nu Lá th hi n hoán v th t 7
9. Cây Quy ết Định – Ví Dụ Sp xp Th m các nút: , , () So sánh: , , () 8
10. Cây Quy ết Định – Ví Dụ Sp xp Mi lá là mt hoán v th hi n th t () Có 3 ph n t, s l ng hoán v (lá) là lá 9
11. Cây Quy ết Định – Mô Hình Có th s d ng cây quy t nh mô ph ng quá trình th c hi n c a b t ký thu t toán s p x p so sánh nào:
    Mt cây cho m i d li u u vào c .
    Cây ch a thông tin các b c so sánh.
    Th i gian ch y c a thu t toán là dài ng i t g c n lá.
    Th i gian ch y x u nh t là cao cây 10
12. Cây Quy ết Định – Ch ặn Dướ i Sắp Xếp
    nh lý:
    Bt c cây quy t nh có th sp xp ph n t có cao ( log )
    Ch ng minh:
    Cây quy t nh cao ℎ, vi lá
    Mi hoán v ca ! nm ti mt lá nào ó
    Do ó ! ≤
    Cây nh phân cao ℎ có nhi u nh t 2 lá.
    Do ó ! ≤ ≤ 2. ℎ ≥ log ! = ( log ) 11
13. Cây Quy ết Định – Ch ặn Dướ i Sắp Xếp Hệ Qu ả:
    Sp xp cây th t b ph n và sp xp gp là thu t toán sp xp so sánh ti u 12
14. Sắp Xếp Trong Th ời Gian Tuy ến Tính
    Sp xp không da trên so sánh gi a các ph n t
    Không áp dng ch n d i log
    Ví d
    Sp xp m (Counting sort)
    Sp x p c ơ s (Radix sort)
    Sp x p gi (Bucket sort) 13
15. Sắp Xếp Đếm (Counting Sort)
    Gi thi t
    Ph n t là s nguyên trong kho ng [1, ]
    Khi = , th i gian ch y
    Ý t ng
    Vi mi ph n t , xác nh s ph n t <
    Ví d:
    có 17 ph n t nh hơn
    s c xp vào v trí th 18
    Nu có các ph n t trùng nhau, không th xp vào cùng v trí 14
16. Sắp Xếp Đếm – Mã Gi ả for ← 1 to do [] ← 0 for ← 1 to do [[]]← [[]]+ 1 for ← 2 to do []← []+ [–1] for ← downto 1 do [[[]]]← [] [[]]← [[]]–1 15
17. Sắp Xếp Đếm – Phân Tích for ← 1 to do () [] ← 0 for ← 1 to do () [[]]← [[]]+ 1 for ← 2 to do () []← []+ [–1] for ← downto 1 do () [[[]]]← [] [[]]←[[]]–1 =(+) 16
18. Sắp Xếp Đếm – Minh Họa
    Input: [1. . ], v i [] ∈ {1, 2, , }
    Output: [1. . ], c sp xp
    B nh ph 1. . m s ph n t
    = tơ ng ng ph n t có giá tr xu t hi n ln
    Minh ha: = 4, 1, 3, 4, 3 17
19. Sắp Xếp Đếm – Minh Họa = 4, 1, 3, 4, 3 18
20. Sắp Xếp Đếm – Bài Tập 6,0,2,0,1,3,4,6,1,3,2 19
21. Sắp Xếp Ổn Định
    m bo th t ban u ca các ph n t bng nhau
    Sp xp m là sp xp n nh
    Thu t toán sp xp nào có tính ch t này?
    Sp xp chèn
    Sp xp la ch n
    Sp xp gp
    Sp xp nhanh 20
22. Sắp Xếp Cơ Số (Radix Sort)
    Sp xp theo tng cơ s
    Bt u t cơ s ít quan tr ng nh t
    S dng sp xp n nh sp xp mi cơ s 21
23. Sắp Xếp Cơ Số – Minh Họa 22
24. Sắp Xếp Cơ Số – Th ời Gian Ch ạy
    Ph thu c vi c la ch n thu t toán nào sp xp cơ s.
    Ch n sp xp m: + 23
25. Sắp Xếp Gi ỏ (Bucket Sort)
    Gi thi t d li u trong kho ng [0, 1)
    To ng u nhiên
    Phân b ng u
    c lp vi nhau
    Ý t ng
    Chia kho ng d li u thành ph n bng nhau
    Phân b d li u vào các gi
    Sp xp tng gi
    Li t kê ph n t trong gi 24
26. Sắp Xếp Gi ỏ
    Tr ng hp tt nh t, mi d li u c phân vào mt gi
    Tr ng hp khác, sp xp tng gi s dng sp xp chèn
    D li u không phân b ng u
    Xác nh kho ng ca mi gi
    Sau khi phân b d li u vào gi , c mi gi tơ ng ơ ng nhau 25