tailieunhanh - Bài giảng Cấu trúc dữ liệu: Chương 13 - Nguyễn Xuân Vinh

Bài giảng Cấu trúc dữ liệu - Chương 13: Tìm kiếm trình bày về định nghĩa giải thuật tìm kiếm, phân loại tìm kiếm, giải thuật, cài đặt và độ phức tạp của các loại tìm kiếm. Hy vọng đây là tài liệu tham khảo hữu ích cho bạn. | TÌM KIẾM Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Định nghĩa Giải thuật tìm kiếm là một thuật toán trả về kết quả là một lời giải cho bài toán đó. Trong giải thuật tìm kiếm người ta thường cân nhắc giữa các lời giải có thể và tìm ra lời giải tối ưu nhất. Không gian tìm kiếm: tập hợp các lời giải có thể đối với 1 bài toán. 2 Phân loại tìm kiếm Tìm kiếm không có thông tin Tìm kiếm trên danh sách TÌm kiếm trên cây Tìm kiếm trên đồ thị TÌm kiếm có thông tin Tìm kiếm đối kháng Thỏa mãn ràng buộc 3 Tìm kiếm không có thông tin Một giải thuật không tính đến bản chất cụ thể của bài toán. Ưu điểm: Có thể được sử dụng cho nhiều bài toán. Nhược điểm: Không gian tìm kiếm rất lớn. Thời gian tìm kiếm lâu. 4 Tìm kiếm trên danh sách Tìm một khóa nào đó trong 1 tập hợp các phần tử nào đó. Các thuật toán: Tìm kiếm tuyến tính – linear search Tìm kiếm nhị phân – binary search Tìm kiếm nội suy – interpolation search Fibonaccian search Jump . | TÌM KIẾM Teacher: Nguyễn Xuân Vinh Email: nguyenxuanvinh@ CẤU TRÚC DỮ LIỆU DATA STRUCTURES [214331] Định nghĩa Giải thuật tìm kiếm là một thuật toán trả về kết quả là một lời giải cho bài toán đó. Trong giải thuật tìm kiếm người ta thường cân nhắc giữa các lời giải có thể và tìm ra lời giải tối ưu nhất. Không gian tìm kiếm: tập hợp các lời giải có thể đối với 1 bài toán. 2 Phân loại tìm kiếm Tìm kiếm không có thông tin Tìm kiếm trên danh sách TÌm kiếm trên cây Tìm kiếm trên đồ thị TÌm kiếm có thông tin Tìm kiếm đối kháng Thỏa mãn ràng buộc 3 Tìm kiếm không có thông tin Một giải thuật không tính đến bản chất cụ thể của bài toán. Ưu điểm: Có thể được sử dụng cho nhiều bài toán. Nhược điểm: Không gian tìm kiếm rất lớn. Thời gian tìm kiếm lâu. 4 Tìm kiếm trên danh sách Tìm một khóa nào đó trong 1 tập hợp các phần tử nào đó. Các thuật toán: Tìm kiếm tuyến tính – linear search Tìm kiếm nhị phân – binary search Tìm kiếm nội suy – interpolation search Fibonaccian search Jump search Secant search Bảng băm – hashtable Cây tìm kiếm nhị phân cân bằng – self-balancing binary search tree 5 Tìm kiếm tuyến tính – linear search Ý tưởng của thuật toán: Thuật toán tiến hành kiểm tra từng phần tử trong danh sách theo thứ tự của danh sách đó. Ưu điểm: Đơn giản, dễ cài đặt Có thể áp dụng cho 1 danh sách bất kỳ mà không cần tiền xử lý. Nhược điểm: Thời gian chạy lớn: Trường hợp trung bình và xấu nhất O(n). Trường hợp tốt nhất O(1). 6 Minh họa tìm x =10 Minh họa tìm x = 25 7 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 10 10 7 5 12 41 10 32 13 9 15 3 1 2 3 4 5 6 7 8 9 10 25 Đã tìm thấy tại vị trí 5 Đã hết mảng Tìm kiếm tuyến tính – linear search 7 Giải thuật Bước 1: i = 1 //bắt đầu từ phần tử đầu tiên của dãy. Bước 2: so sánh a[i] với x, có 2 khả năng: a[i] = x: tìm thấy, dừng thuật toán. a[i] != x: sang bước 3. Bước 3: i = i+1 //xét phần tử kế tiếp trong mảng Nếu i > n: hết mảng, không tìm thấy, dừng. Ngược lại: .