Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - GV. Nguyễn Minh Thành

Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 Giải Thuật Tìm Kiếm nhằm trình bày về khái niệm giải thuật tìm kiếm, tìm kiến tuyến tính, tìm kiếm nhị phân, bài giảng trình bày súc tích, có ví dụ minh họa giúp các bạn hiểu sâu hơn về giải Thuật Tìm Kiếm.
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: Chương 2 - GV. Nguyễn Minh Thành Chương 2 (1) : Giải Thuật Tìm Kiếm Giảng viên : Nguyễn Minh Thành Email : thanhnm@itc.edu.vn Nội Dung I. Giới thiệu II. Giải thuật tìm kiếm III. Tìm kiếm tuyến tính IV. Tìm kiếm nhị phân 2 Nguyễn Minh Thành I. Giới Thiệu  Tìm kiếm : là duyệt một danh sách và lấy ra phần tử thoả tiêu chuẩn cho trước  Là một thao tác phổ biến trên máy tính và trong các ứng dụng  Tìm kiếm 1 dòng trong CSDL  Tìm kiếm hồ sơ, tập tin  Tìm kiếm 1 người trong một danh sách …  Việc tìm kiếm nhanh thông tin trong một lượng lớn thông tin là một điều cần thiết.  Các giải thuật tìm kiếm 3 Nguyễn Minh Thành II. Giải thuật tìm kiếm  Khảo sát việc tìm kiếm thường trên mảng và danh sách.  Có nhiều loại :  Tìm kiếm tuyến tính (tuần tự)  Tìm kiếm nhị phân …  Cấu trúc :  Input  Mảng A gồm n phần tử  Giá trị x cần tìm  Output  Vị trí x trong A hoặc -1 nếu không tồn tại x  Thao tác cơ bản 4  So sánh Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính  Có 2 loại tìm kiếm tuyến tính :  Vét cạn (exhaustive)  Dùng lính canh (sentinel) 5 Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính – Vét Cạn  Thuật toán :  Lần lượt so sánh x với các phần tử của mảng A cho đến khi 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 = 6 6 Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính – Vét Cạn  Cài đặt 1 : int LinearExhaustive(int a[], int N, int x) { int i=0; while ((iIII. Tìm Kiếm Tuyến Tính – Vét Cạn  Cài đặt 2 : int LinearExhaustive(intA[], intn, intx) { for(int i=0; iIII. Tìm Kiếm Tuyến Tính – Vét Cạn  Phép so sánh là phép toán sơ cấp được dùng trong thuật toán-> số lượng các phép so sánh sẽ là thước đo độ phức tạp của thuật toán.  Mỗi vòng lặp có 2 điều kiện cần kiểm tra:  Kiểm tra cuối mảng  Kiểm tra phần tử hiện tại có bằng x hay không?  Trường hợp xấu nhất nằm ở cuối mảng A  Ta có 2*n+1 số phép so sánh  => Số phép so sánh tăng/giảm tuyến tính theo số phần tử  Vậy độ phức tạp của thuật toán là : O(n) 9 Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính – Lính Căn  Trong thuật toán vét cạn, có 2 điều kiện được kiểm tra:  Có thể bỏ việc kiểm tra điều kiện cuối mảng bằng cách dùng “lính canh”.  Lính canh là phần tử có giá trị bằng với phần tử cần tìm và đặt ở cuối mảng.  Thuật toán lính căn 10 Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính – Lính Căn  Thuật toán lính căn  Tìm tuần tự từ đầu mảng cho đến khi tìm thấy x (chắc chắn sẽ tìm thấy x)  Nếu x được tìm thấy tại vị trí lính canh thì x không thuộc mảng A.  Ngược lại trả về vị trí của x trong mảng A. 11 Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính – Lính Căn  Cài đặt 1 : int LinearSentinel(int a[],int N,int x) { int i=0; // mảng gồm N phần tử từ a[0]..a[N-1] a[N] = x; // thêm phần tử thứ N+1 while (a[i]!=x ) i++; if (i==N) return -1; // tìm hết mảng nhưng không có x else return i; // tìm thấy x tại vị trí i } 12 Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính – Lính Căn  Cài đặt 2 : int LinearSentinel(int a[], int n, int x) { a[n] = x; //đặtlínhcanh for (int i=0; ;i++) if (a[i] == x) break; if(i==n) i=-1; return i; } 13 Nguyễn Minh Thành III. Tìm Kiếm Tuyến Tính – Lính Căn  Số phép so sánh trong trường hợp xấu nhất : n+2  Vậy độ phức tạp của thuật toán là O(n)  Tuy nhiên, thực nghiệm cho thấy trong trường hợp n lớn, thời gian tìm kiếm giảm khi dùng phương pháp lính canh.  Với n=15000: nhanh hơn khoảng 20% (0.22s so với 0.28s) 14 Nguyễn Minh Thành IV. Tìm Kiếm Nhị Phân  Khi một mảng đã được sắp thứ tự, tận dụng điều này ta có thể giảm một số thao tác cho thuật toán tìm kiếm.  Thuật toán tìm kiếm nhị phân  Input:  Dãy A, n phần tử đã được sắp xếp  Giá trị x cần tìm  Output: giống với thuật toán tìm kiếm tuần tự 15 Nguyễn Minh Thành IV. Tìm Kiếm Nhị Phân  Ý tưởng  So sánh x với phần tử chính giữa mảng A.  Nếu x là phần tử giữa thì dừng. Nếu không : xác định xem x có thể thuộc nửa trái hay nửa phải của A.  Lặp lại 2 bước trên với nửa đã được xác định. 16 Nguyễn Minh Thành IV. Tìm Kiếm Nhị Phân  Ví dụ : tìm x = 41 x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 Tìm thấy x tại vị trí 6 l m m r m 17 Nguyễn Minh Thành IV. Tìm Kiếm Nhị Phân  Ví dụ : tìm x = 45 x x x x 3 14 16 19 22 41 46 51 63 71 1 2 3 4 5 6 7 8 9 10 l m m r l > r: Kết thúc: Không tìm thấy m m 18 Nguyễn Minh Thành IV. Tìm Kiếm Nhị Phân  Các bước của giải thuật Bước 1: left = 1; right = N; // tìm kiếm trên tất cả các phần tử Bước 2: mid = (left+right)/2; // lấy mốc so sánh So sánh a[mid] với x, có 3 khả năng :  a[mid] = x: Tìm thấy. Dừng  a[mid] > x: //tìm tiếp x trong dãy con aleft .. amid -1 ...