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: Các thuật toán tìm kiếm và sắp xếp cơ bản - Lê Thị Ngọc Hạnh

Chia sẻ: Tằng Túy | Ngày: | Loại File: PDF | Số trang:28

Thêm vào BST
Báo xấu
129
lượt xem 7
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: Các thuật toán tìm kiếm và sắp xếp cơ bản gồm có những nội dung chính sau: Giới thiệu các giải thuật tìm kiếm, tìm kiếm tuần tự, tìm kiếm nhị phân, đánh giá và tổng kết. Mời các bạn cùng tham khảo.

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: Các thuật toán tìm kiếm và sắp xếp cơ bản - Lê Thị Ngọc Hạnh

  1. CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT 1 CÁC THUẬT TOÁN TÌM KIẾM VÀ SẮP XẾP CƠ BẢN Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  2. Nội dung trình bày 2 Giới thiệu các giải thuật tìm kiếm Tìm kiếm tuần tự Tìm kiếm nhị phân Đánh giá và tổng kết Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  3. 1. Giới thiệu thuật toán tìm kiếm 3  Tìm kiếm là thao tác rất phổ biến trong cuộc sống hàng ngày.  Các loại tìm kiếm:  Tìm kiếm tuần tự (Sequential/ Linear Search)  Tìm kiếm nhị phân (Binary Search)  ……  Mục tiêu:  Tìm hiểu về 2 giải thuật 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 với dữ liệu đầu vào. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  4. 2.1. Tìm kiếm tuần tự - Vét cạn 4  Ý tưởng: So sánh x lần lượt với các phần tử của mảng A cho đến khi gặp được phần tử có giá trị x cần tìm, hoặc đã tìm đến hết mảng mà không thấy x.  Minh họa: x = 2827 Có x trong Không tìm thấy x mảngmảng trong 25 7 3 12 27 5 9 8 61 27 28 27 28 27 28 27 28 27 28 28 28 28 28 28 Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  5. 2.1. Tìm kiếm tuần tự - Vét cạn 5  Input:  Mảng A.  n phần tử.  Giá trị x cần tìm  Output:  Nếu x xuất hiện trong A, trả về 1.  Ngược lại, trả về 0. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  6. 2.1. Tìm kiếm tuần tự - Vét cạn 6  Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0  Bước 2: so sánh i và n  Nếu chưa hết mảng (i=n), kết thúc.Trả về 0.  Bước 3: So sánh giá trị A[i] với x  Nếu A[i] bằng x: kết thúc. Trả về 1.  Nếu A[i] khác x, tăng i thêm 1 và quay lại bước 2. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  7. 2.1. Tìm kiếm tuần tự - Vét cạn 7 Bắt đầu Lưu đồ thuật toán Nhập A, n, x i=0 Đ Kết i>=n thúc S Đ A[i] = x S i = i+1 Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  8. 2.1. Tìm kiếm tuần tự - Vét cạn 8  Mỗi vòng lặp, có 2 điều kiện cần kiểm tra:  Kiểm tra đã duyệt hết mảng? (bước 2)  Kiểm tra phần tử hiện tại có bằng x?(bước 3)  Số phép so sánh trung bình: 2(1+2+3+…+n)/n = n+1  Số phép so sánh tăng/giảm tuyến tính theo số phần tử. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  9. 2.1. Tìm kiếm tuần tự - Vét cạn 9  Độ phức tạp của thuật toán:  Tốt nhất: O(1)  Trung bình: O(n)  Xấu nhất: O(n) Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  10. 2.2. Tìm kiếm tuần tự - Lính canh 10  Có thể bỏ qua 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à được đặt ở cuối mảng. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  11. 2.2. Tìm kiếm tuần tự - Lính canh 11 Ví dụ: A = {25, 6, 18, 4}; x = 7 (1) 25 6 18 4 7 (2) 25 6 18 4 7 x=7 x=7 (3) 25 6 18 4 7 (4) 25 6 18 4 7 x=7 i=4 x=7 (i>n) (5) 25 6 18 4 7 x=7 Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  12. 2.2. Tìm kiếm tuần tự - Lính canh 12  Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0  Bước 2: So sánh giá trị A[i] với giá trị x  Nếu A[i] khác x, tăng i thêm 1 và quay lại bước 2.  Nếu A[i] bằng x: • Nếu i=n: kết thúc, trả về 0. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  13. Task 13  Task 1: Cài đặt thuật toán tìm kiếm theo cách vét cạn và sử dụng lính canh.  Task 2: Xây dựng thuật toán và cài đặt chương trình tìm những vị trí mà x xuất hiện trong mảng cho trước.  Task 3: Xây dựng thuật toán và cài đặt chương trình tìm xem trong mảng cho trước có phần tử nào là số chẵn hay không? Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  14. 3. Tìm kiếm nhị phân (Binary Search)14 Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  15. Thuật toán tìm kiếm nhị phân 15  Với dãy A được sắp xếp tuần tự (tăng/giảm) thì độ phức tạp của thuật toán tìm kiếm tuần tự không đổi.  Tận dụng thông tin của mảng đã được sắp xếp để giới hạn vùng tìm kiếm của giá trị cần tìm trong mảng.  Thuật toán tìm kiếm nhị phân. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  16. Thuật toán tìm kiếm nhị phân 16  Input:  Mảng A với n phần tử đã được sắp xếp.  Giá trị x cần tìm.  Output:  Nếu x xuất hiện trong A, trả về 1.  Ngược lại, trả về 0. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  17. Thuật toán tìm kiếm nhị phân 17 Ý tưởng:  So sánh x với giá trị của phần tử chính giữa của mảng A.  Nếu x là phần tử chính giữa thì dừng.  Nếu không, xác định xem x thuộc nửa trái hay nửa phải của phần tử chính giữa.  Lặp lại 2 bước trên với nửa đã được xác định. Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
  18. Thuật toán tìm kiếm nhị phân 18  Bước 1: left = 0; right = n-1;  Bước 2: mid = (left + right)/2; 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: right = mid - 1;  A[mid] < x: left = mid + 1;  Bước 3: Nếu left
  19. Thuật toán tìm kiếm nhị phân 19 Minh họa: mid=(0+2)/2=1 mid=(0+6)/2=3 mid mid A[] = {4, 8, 15, 17, 32, 59, 72}, x = 8. Index 0 1 2 3 4 5 6 A[i] 4 8 15 17 32 59 72 Lần 1 left right Lần 2 x
  20. Thuật toán tìm kiếm nhị phân 20 Minh họa: mid=(4+6)/2=5 mid=(6+6)/2=6 mid mid=(0+6)/2=3 mid A[] = {4, 8, 15, 17, 32, 59, 72}, x = 73 72 Index 0 1 2 3 4 5 6 A[i] 4 8 15 17 32 59 72 Lần 1 left left right Lần 2 left right x>A[3] Lần 3 x>A[5] Tìm thấy Không tìmx thấy trongx x=A[6] x>A[6] left>right A, kết trong thúc A, kết thúc Các thuật toán tìm kiếm và sắp xếp cơ bản 8/27/2015
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