Bài giảng "Thiết kế và đánh giá thuật toán: Chặn dưới sắp xếp" cung cấp cho người học các kiến thức: Chặn trên, chặn dưới, sắp xếp trong thời gian tuyến tính. nội dung chi tiết. | 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 .
