Bài giảng Thiết kế và đánh giá thuật toán: Chặn dưới sắp xếp - TS. Lê Nguyên Khôi

Thiết Kế & Đánh Giá Thuật Toán<br /> Chặn Dưới Sắp Xếp<br /> TS. Lê Nguyên Khôi<br /> Trường Đại Học Công Nghệ - ĐHQGHN<br /> <br /> Nội Dung<br /> Chặn trên (upper bound -
)<br />
Chặn dưới (lower bound - )<br />
Sắp xếp trong thời gian tuyến tính<br />
<br /> <br /> Sắp xếp đếm (Counting sort)<br />
Sắp xếp cơ số (Radix sort)<br />
Sắp xếp giỏ (Bucket sort)<br />
<br /> <br /> 1<br /> <br /> Chặn Trên<br /> Bài toán X: dữ liệu đầu vào  xây dựng<br /> thuật toán chạy trong thời gian
(())<br />
(): thể hiện độ phức tạp (hay độ khó)<br /> để giải bài toán X<br />
Mục tiêu: xác định   càng nhỏ càng tốt<br />
Chặn trên (
) giúp xác định giải bài toán<br /> X khó cỡ nào<br />
<br /> <br /> 2<br /> <br /> Chặn Dưới<br /> Giải bài toán X, bất cứ thuật toán nào<br /> cũng chạy trong thời gian (())<br />
Mục tiêu: xác định   càng lớn càng tốt<br />
Chặn dưới () giúp xác định thuật toán<br /> giải bài toán X đã đủ tốt chưa<br />
Ví dụ:<br />
<br /> <br /> Thuật toán chạy trong thời gian
( log   )<br />
Chặn dưới ( log ) để giải bài toán<br />
Cải tiến thuật toán để thu hẹp khoảng log <br />
<br /> <br /> 3<br /> <br /> Chặn Của Sắp Xếp<br />
<br /> <br /> Chặn trên
<br /> <br /> <br /> <br /> <br /> / dưới<br /> <br /> <br /> ( )<br /> <br /> Nổi bọt (bubble sort)<br />
Chèn (insertion sort)<br />
Lựa chọn (selection sort)<br />
<br /> <br />
<br /> <br /> Chặn trên
 log  / dưới ( log )<br />
Gộp<br /> <br /> (merge sort)<br />
Cây thứ tự bộ phận (heap sort)<br />
Nhanh (quick sort) – trường hợp trung bình<br /> <br /> 4<br /> <br />