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
lượt xem 7
download
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.
Bình luận(0) Đăng nhập để gửi bình luận!
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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
- 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
CÓ THỂ BẠN MUỐN DOWNLOAD
-
Bài giảng Cấu trúc dữ liệu cơ bản và giải thuật - Chương 1
9 p | 258 | 29
-
Bài giảng Cấu trúc dữ liệu - Bài 1:Tổng quan về cấu trúc dữ liệu và giải thuật
47 p | 176 | 17
-
Bài giảng Cấu trúc dữ liệu: Chương 10 - Nguyễn Xuân Vinh
31 p | 95 | 10
-
Bài giảng Cấu trúc dữ liệu 1: Chương 1 - Lương Trần Hy Hiến
7 p | 162 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật trong C++ - Bài 8: Cấu trúc dữ liệu ngăn xếp
28 p | 81 | 9
-
Bài giảng Cấu trúc dữ liệu giải thuật: Các kiểu dữ liệu trừu tượng cơ bản - Cấu trúc dữ liệu tuyến tính
92 p | 117 | 9
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây đỏ đen - Bùi Tiến Lên
25 p | 87 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Bài 17: Cấu trúc dữ liệu dạng cây
21 p | 77 | 8
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các cấu trúc dữ liệu
193 p | 61 | 7
-
Bài giảng Cấu trúc dữ liệu: Chương Giới thiệu - Nguyễn Xuân Vinh
8 p | 112 | 7
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (2016)
62 p | 94 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 - Trần Minh Thái (Trường Đại học Hồng Bàng )
62 p | 170 | 6
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Cấu trúc dữ liệu cây - Bùi Tiến Lên
68 p | 40 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật – Chương 1: Tổng quan về giải thuật và cấu trúc dữ liệu
10 p | 69 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 1 – Trần Minh Thái (2017)
67 p | 107 | 4
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Chương 2 - Th.S Thiều Quang Trung
41 p | 70 | 3
-
Bài giảng Cấu trúc dữ liệu và giải thuật: Các khái niệm cơ bản
23 p | 48 | 3
-
Bài giảng Cấu trúc dữ liệu giải thuật: Cấu trúc dữ liệu
17 p | 52 | 2
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