Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 9: Chặn dưới sắp xếp - Lê Nguyên Khôi

Giả thiết dữ liệu trong khoảng [0, 1) Tạo ngẫu nhiên Phân bố đồng đều Độc lập với nhau Ý tưởng Chia khoảng dữ liệu thành phần bằng nhau Phân bố dữ liệu vào các giỏ Sắp xếp từng giỏ Liệt kê phần tử trong giỏ Sắp Xếp Giỏ Trường hợp tốt nhất, mỗi dữ liệu được phân vào một giỏ Trường hợp khác, sắp xếp từng giỏ sử dụng sắp xếp chèn Dữ liệu không phân bố đồng đều Xác định khoảng của mỗi giỏ Sau khi phân bố dữ liệu vào giỏ, cỡ mỗi giỏ tương đương nhau

pdf26 trang | Chia sẻ: thucuc2301 | Lượt xem: 682 | Lượt tải: 0download
Bạn đang xem trước 20 trang tài liệu Giáo trình Thiết kế & Đánh giá thuật toán - Bài giảng 9: Chặn dưới sắp xếp - Lê Nguyên Khôi, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
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 Nội Dung  Chặn trên (upper bound - )  Chặn dưới (lower bound - )  Sắp xếp trong thời gian tuyến tính  Sắp xếp đếm (Counting sort)  Sắp xếp cơ số (Radix sort)  Sắp xếp giỏ (Bucket sort) 1 Chặn Trên  Bài toán X: dữ liệu đầu vào  xây dựng thuật toán chạy trong thời gian (())  (): thể hiện độ phức tạp (hay độ khó) để giải bài toán X  Mục tiêu: xác định   càng nhỏ càng tốt  Chặn trên () giúp xác định giải bài toán X khó cỡ nào 2 Chặn Dưới  Giải bài toán X, bất cứ thuật toán nào cũng chạy trong thời gian (())  Mục tiêu: xác định   càng lớn càng tốt  Chặn dưới () giúp xác định thuật toán giải bài toán X đã đủ tốt 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  Cải tiến thuật toán để thu hẹp khoảng log  3 Chặn Của Sắp Xếp  Chặn trên   / dưới ( )  Nổi bọt (bubble sort)  Chèn (insertion sort)  Lựa chọn (selection sort)  Chặn trên   log  / dưới ( log ) Gộp (merge sort)  Cây thứ tự bộ phận (heap sort)  Nhanh (quick sort) – trường hợp trung bình 4 Chặn Dưới Sắp Xếp  Các thuật toán sắp xếp vừa đề cập:  Đều dựa trên so sánh giữa các phần tử  Chặn dưới ( log )  Sắp xếp so sánh (comparison-based sort)  Không khác biệt về độ phức tạp  Khác biệt về thời gian chạy theo một hằng số  Một số thuật toán không dựa trên so sánh giữa các phần tử  Không áp dụng chặn dưới ( log ) 5 Chặn Dưới Sắp Xếp – Chứng Minh  Sử dụng mô hình Cây Quyết Định  Cây nhị phân  Nút trong ứng với phép so sánh 2 phần tử  Nhánh trái ứng với kết quả nhỏ hơn bằng  Nhánh phải ứng với kết quả lớn hơn  Lá ứng với lời giải (thứ tự các phần tử) 6 Cây Quyết Định Sắp xếp 〈,  , , 〉 Nút trong :  với ,  ∈ 1, 2, ,  thể hiện so sánh  với  Cây con trái thể hiện các bước so sánh nếu    Cây con phải thể hiện các bước so sánh nếu    Lá thể hiện hoán vị thứ tự 7           Cây Quyết Định – Ví Dụ Sắp xếp ,  ,   6,8,5 Thăm các nút: 1: 2 , 2: 3 , 1: 3 ⇒ (312) So sánh: 6 % 8 , 8  5 , 6 % 5 ⇒ (5 % 6 % 8) 8           Cây Quyết Định – Ví Dụ Sắp xếp ,  ,   6,8,5 Mỗi lá là một hoán vị & 1 , & 2 , , &  thể hiện thứ tự '()  '  ⋯  '  Có 3 phần tử, số lượng hoán vị (lá) là 3!  6 lá 9           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:  Một 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 Cây Quyết Định – Chặn Dưới Sắp Xếp  Định lý:  Bất cứ cây quyết định có thể sắp xếp  phần tử có độ cao ( log )  Chứng minh:  Cây quyết định độ cao ℎ, với + lá Mỗi hoán vị của ! nằm tại một lá nào đó Do đó ! ≤ +  Cây nhị phân độ cao ℎ có nhiều nhất 2, lá.  Do đó ! ≤ + ≤ 2,. ℎ ≥ log ! = ( log ) 11 Cây Quyết Định – Chặn Dưới Sắp Xếp Hệ Quả:  Sắp xếp cây thứ tự bộ phận và sắp xếp gộp là thuật toán sắp xếp so sánh tối ưu 12 Sắp Xếp Trong Thời Gian Tuyến Tính  Sắp xếp không dựa trên so sánh giữa các phần tử  Không áp dụng chặn dưới   log   Ví dụ  Sắp xếp đếm (Counting sort)  Sắp xếp cơ số (Radix sort)  Sắp xếp giỏ (Bucket sort) 13 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 1   Ý tưởng  Với mỗi phần tử 2, xác định số phần tử < 2  Ví dụ: có 17 phần tử nhỏ hơn 2 2 sẽ được xếp vào vị trí thứ 18  Nếu có các phần tử trùng nhau, không thể xếp vào cùng vị trí 14 Sắp Xếp Đếm – Mã Giả for  ← 1 to / do 4[] ← 0 for  ← 1 to  do 4[6[]] ← 4[6[]] + 1 for  ← 2 to / do 4[] ← 4[] + 4[– 1] for  ←  downto 1 do 9[4[6[]]] ← 6[] 4[6[]] ← 4[6[]] – 1 15 Sắp Xếp Đếm – Phân Tích for  ← 1 to / do 1(/) 4[] ← 0 for  ← 1 to  do 1() 4[6[]] ← 4[6[]] + 1 for  ← 2 to / do 1(/) 4[] ← 4[] + 4[– 1] for  ←  downto 1 do 1() 9[4[6[]]] ← 6[] 4[6[]] ← 4[6[]] – 1 = 1( + /) 16 Sắp Xếp Đếm – Minh Họa  Input: 6[1 . . ], với 6[] ∈ {1, 2, , /}  Output: 9[1 . . ], được sắp xếp  Bộ nhớ phụ 4 1 . .  đếm số phần tử 4  =  tương ứng phần tử có giá trị  xuất hiện  lần  Minh họa: 6 = 4, 1, 3, 4, 3 17 6 = 4, 1, 3, 4, 3 Sắp Xếp Đếm – Minh Họa 18 Sắp Xếp Đếm – Bài Tập 6  6, 0, 2, 0, 1, 3, 4, 6, 1, 3, 2 19 Sắp Xếp Ổn Định  Đảm bảo thứ tự ban đầu của các phần tử bằng nhau  Sắp xếp đếm là sắp xếp ổn định  Thuật toán sắp xếp nào có tính chất này? Sắp xếp chèn Sắp xếp lựa chọn Sắp xếp gộp Sắp xếp nhanh 20 Sắp Xếp Cơ Số (Radix Sort)  Sắp xếp theo từng cơ số  Bắt đầu từ cơ số ít quan trọng nhất  Sử dụng sắp xếp ổn định để sắp xếp mỗi cơ số 21 Sắp Xếp Cơ Số – Minh Họa 22 Sắp Xếp Cơ Số – Thời Gian Chạy  Phụ thuộc việc lựa chọn thuật toán nào để sắp xếp cơ số.  Chọn sắp xếp đếm: 1 >  + / 23 Sắp Xếp Giỏ (Bucket Sort)  Giả thiết dữ liệu trong khoảng [0, 1)  Tạo ngẫu nhiên  Phân bố đồng đều  Độc lập với nhau  Ý tưởng  Chia khoảng dữ liệu thành  phần bằng nhau  Phân bố  dữ liệu vào các giỏ  Sắp xếp từng giỏ  Liệt kê phần tử trong giỏ 24 Sắp Xếp Giỏ  Trường hợp tốt nhất, mỗi dữ liệu được phân vào một giỏ  Trường hợp khác, sắp xếp từng giỏ sử dụng sắp xếp chèn  Dữ liệu không phân bố đồng đều  Xác định khoảng của mỗi giỏ  Sau khi phân bố  dữ liệu vào giỏ, cỡ mỗi giỏ tương đương nhau 25

Các file đính kèm theo tài liệu này:

  • pdfthiet_ke_danh_gia_thuat_toanbaigiang09_chanduoisapxep_0642_2032096.pdf