Bài giảng Cấu trúc dữ liệu và giải thuật: Các chiến lược tìm kiếm - ĐH KHTN TPHCM

Bài giảng Cấu trúc dữ liệu và giải thuật: Các chiến lược tìm kiếm gồm có những nội dung cụ thể sau: Giới thiệu các thao tác tìm kiếm phổ biến trong cuộc sống hàng ngày, các thuật toán tìm kiếm, tìm kiếm trình tự, thuật toán lính canh, tìm kiếm nhị phân và các thuật toán tìm kiếm nhị phân. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Bài giảng Cấu trúc dữ liệu và giải thuật: Các chiến lược tìm kiếm - ĐH KHTN TPHCMGiảng viên:Văn Chí Nam – Nguyễn Thị Hồng Nhung – Đặng Nguyễn Đức Tiến2Giới thiệuTìm kiếm tuần tựTìm kiếm nhị phânTìm kiếm theo bảng bămTổng kếtCấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 201113Thao tác tìm kiếm rất phổ biến trong cuộc sốnghàng ngày. Tìmkiếm hồ sơ, tập tin. Tìm kiếm tên người trong danh sách.…Cấu trúc dữ liệu và giải thuật – HCMUS 20114Có nhiều loại: Tìmkiếm tuần tự (Sequential/ Linear Search) Tìm kiếm nhị phân (Binary Search) …Mục tiêu: Tìmhiểu về 2 thuật toán tìm kiếm cơ bản. Phân tích thuật toán để lựa chọn thuật toán phù hợp khiáp dụng vào thực tế.Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 201125Sequential SearchLinear SearchCấu trúc dữ liệu và giải thuật – HCMUS 20116Input: Dãy A,n phần tử Giá trị x cần tìmOutput: Nếux xuất hiện trong A: trả về vị trí xuất hiện đầu tiêncủa x Nếu không: trả về n hoặc -1Thuật toán: Vétcạn (exhaustive) Dùng lính canh (sentinel)Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 201137Thuật toán: Lầnlượt so sánh x với các phần tử của mảng A cho đếnkhi gặp được phần tử cần tìm, hoặc hết mảng. Ví dụ: A = {1, 25, 6, 5, 2, 37, 40}, x = 6x = 612565237406523740523740x = 6125x = 61256Dừng8Thuật toán: LinearExhaustive• Bước 1. Khởi tạo biến chỉ số: i = 0• Bước 2. Kiểm tra xem có thực hiện hết mảng haychưa: So sánh i và n•••Nếu chưa hết mảng (i < n), sang bước 3.Nếu đã hết mảng (i >= n), thông báo không tìm thấygiá trị x cần tìm.Bước 3. So sánh giá trị a[i] với giá trị x cần tìm••Nếu a[i] bằng x: Kết thúc chương trình và thông báođã tìm thấy x.Nếu a[i] khác x, tăng i thêm 1 và quay lại bước 2.Cấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 201149Nhận xét: Phép so sánh là phép toán sơ cấpđược dùng trong thuật toán. Suy ra, số lượngcác phép so sánh sẽ là thước đo độ phức tạpcủa thuật toán.Mỗi vòng lặp có 2 điều kiện cần kiểm tra: Kiểmtra cuối mảng (bước 2) Kiểm tra phần tử hiện tại có bằng x? (bước 3)Cấu trúc dữ liệu và giải thuật – HCMUS 201110Trường hợp x nằm ở 2 biên của mảng A: rấthiếm khi xuất hiện. Ước lượng số vòng lặp trung bình sẽ hữu íchhơn. Số phép so sánh trung bình:2(1+2+ … + n)/n = n+1=> Số phép so sánh tăng/giảm tuyến tính theo sốphần tửCấu trúc dữ liệu và giải thuật – HCMUS 2011© FIT-HCMUS 20115