tailieunhanh - Bài giảng Phân tích và thiết kế thuật toán: Đánh giá một số thuật toán thông dụng - Phạm Thế Bảo

Bài giảng Phân tích và thiết kế thuật toán này trình bày về đánh giá một số thuật toán thông dụng. Nội dung chính của bài giảng gồm có: Tìm kiếm tuần tự, xem xét phân bố khóa, tìm kiếm nhị phân, sắp xếp chèn,. . | 28 03 2008 ĐÁNH GIÁ MỘT SỐ THUẬT TOÁN THÔNG DỤNG Phạm Thế Bảo Khoa Toán - Tin học Trường Đại học Khoa học Tự nhiên T 1 1 Ấ . Ă . Tìm kiêm tuần tự Xét một mảng các phần tử a 1 a 2 . a n . Phần tử a i có khóa tìm kiêm là a i .key bài toán cho trước khóa k có tồn tại j để a j .key bằng k hay không i 1 found false while i n not found do if a i .key bằng k then found true Nếu bỏ else else 1. Thuật toán còn đúng không i i 1 2. Có tăng phép đếm gán endif endw Phạm Thế Bảo 1 28 03 2008 Ta cần phân biệt Phép toán số học so sánh gán Phép toán trên khóa sao chép so sánh Nếu ta thêm một phần tử a n 1 .key k thì số phép toán sẽ tăng hay giảm Viết lại thuật toán i 1 a n 1 .key k while a i .key khác k do i i 1 endw Phạm Thế Bảo Thuật toán dừng khi nào - i n 1 - không tìm thấy - i i0 với 1 i0 n - tìm thấy Để đánh giá ta cần tính a - Tìm không thấy kỂ a i .key i a n gọi q là xác suất tìm không thấy. - Tìm thấy sẽ có xác suất là 1-q - Đặt pi là xác suất để a i .key bằng k - Giả thiết a k .key khác a l .key nếu k l - Nếu a i .key bằng k thì a i-1 n - Vậy q 1 - q S Pi 1 va có atrung bình a s Pi i - 1 i 1 i 1 Phạm Thế Bảo 2 28 03 2008 Khi tìm thấy số lượng so sánh khóa - Tối thiểu 1 - Tối đa n - Trung bình a 1 2 Pi Số lần so sánh khóa trung bình cho cả hai trường hợp tìm thấy và không tìm thấy là n Ị 1 - q p i 1 Phạm Thế Bảo J 1 1 Ấ 1 1 r Xem xét phân bố khóa 1. Giả sử a i .key i k được chọn ngẫu nhiên từ tập hợp 1 2 2 3 3 3 . i i . c . n . n n 1 n 2 . 2n ----Ị-- r i lần--n lần n n 3 Tông số khả năng có thể là 1 2 . n n -y n _ 2 2 Xác suất để kế key là q nn 3 n 3 2 Suy ra i 2i p n n 1 n n 1 2 Phạm Thế Bảo