intTypePromotion=1
zunia.vn Tuyển sinh 2024 dành cho Gen-Z zunia.vn zunia.vn
ADSENSE
 » 
 » 

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

Chia sẻ: Cxzvscv Cxzvscv | Ngày: | Loại File: PDF | Số trang:23

Thêm vào BST
Báo xấu
97
lượt xem 5
download
 
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: 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

  1. 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
  2. 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
  3. 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
  4. 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
  5. 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
  6. 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
  7. 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 ((i
  8. III. 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; i
  9. III. 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
  10. 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
  11. 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
  12. 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
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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 right =mid - 1;  a[mid] < x: //tìm tiếp x trong dãy con amid +1 .. aright left = mid + 1; Bước 3: Nếu left
  20. IV. Tìm Kiếm Nhị Phân  Cài đặt 1 int BinarySearch(int a[],int N,int x ) { int left =0; right = N-1; int mid; do{ mid = (left + right)/2; if (x == a[mid]) return mid;//Thấy x tại mid else if (x < a[mid]) right = mid -1; else left = mid +1; }while (left
ADSENSE

CÓ THỂ BẠN MUỐN DOWNLOAD

THÔNG TIN
TRỢ GIÚP
HỖ TRỢ KHÁCH HÀNG
Theo dõi chúng tôi

Chịu trách nhiệm nội dung:

Nguyễn Công Hà - Giám đốc Công ty TNHH TÀI LIỆU TRỰC TUYẾN VI NA

LIÊN HỆ

Địa chỉ: P402, 54A Nơ Trang Long, Phường 14, Q.Bình Thạnh, TP.HCM

Hotline: 093 303 0098

Email: support@tailieu.vn

Giấy phép Mạng Xã Hội số: 670/GP-BTTTT cấp ngày 30/11/2015 Copyright © 2022-2032 TaiLieu.VN. All rights reserved.

 

Đồng bộ tài khoản
2=>2