Tìm kiếm - Searching Trình bày các thuật toán thông dụng cho việc tìm kiếm (Tìm

Chia sẻ: Nguyễn Hữu Thiên Sơn | Ngày: | Loại File: PDF | Số trang:5

Thêm vào BST

Báo xấu

86
lượt xem 8
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tìm kiếm - Searching Trình bày các thuật toán thông dụng cho việc tìm kiếm (Tìm tuần tự, tìm nhị phân) p Minh họa các thuật toán p Đánh giá thuật toán p Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 1 Công dụng p Tìm kiếm trong một danh sách các phần tử là một thao tác thường sử dụng trên máy tính p Ví dụ: p Cơ sở dữ liệu (Database): tìm 1 sinh viên, tìm 1 tài khoản ngân hàng,… p Internet: Yahoo!, Google,… Spring 2004 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM 2 1 Các phương...

Chủ đề:

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

Lưu

Nội dung Text: Tìm kiếm - Searching Trình bày các thuật toán thông dụng cho việc tìm kiếm (Tìm

Tìm kiếm - Searching Trình bày các thuật toán p thông dụng cho việc tìm kiếm (Tìm tuần tự, tìm nhị phân) p Minh họa các thuật toán p Đánh giá thuật toán Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 1 Công dụng kiếm trong một danh sách các phần tử p Tìm là một thao tác thường sử dụng trên máy tính p Ví dụ: p Cơ sở dữ liệu (Database): tìm 1 sinh viên, tìm 1 tài khoản ngân hàng,… p Internet: Yahoo!, Google,… Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 2 1
Các phương pháp phổ biến tuần tự (Serial Search) p Tìm p Đơn giản p Chi phí O(n) nhị phân p Tìm p Phải là 1 danh sách “đặc” p Dữ liệu cần được sắp thứ tự p Chi phí trung bình O(log2n) Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 3 Tìm tuần tự (Serial Search) int SerialSearch(int a[], int n, int key) { for (int i=0; i < n; i++) if (a[i]==key) return i; // tìm thấy // không tìm thấy return –1; } Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 4 2
Serial Search Đánh giá thuật toán thước của dãy: n p Kích p Trường hợp tốt nhất: O(1), key==a[0] p Trường hợp xấu nhất: O(n), key==a[n-1] hoặc không tìm thấy p Trường hợp trung bình: hơn O(n) p ít p Chính xác là bao nhiêu ? Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 5 Serial Search Trường hợp trung bình p Giả sử: p phần tử cần tìm key có trong dãy p xác suất xuất hiện tại các vị trí trong dãy là nh ư nhau p Chi phí trung bình: 1 + 2 + 3 + ... + n n(n + 1) / 2 (n + 1) = = n n 2 Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 6 3
Tìm nhị phân (Binary Search) Các phần tử được sắp p 2 3 6 7 10 12 16 18 p n=8 p key = 16 [0] [1] [2] [3] [4] [5] [6] [7] Xét phần tử giữa p m = n/2 Nếu (a[m]==key) p à Kết thúc ! Nếu (key < a[m]) p Xét ½ dãy bên trái Nếu (key > a[m]) p Xét ½ dãy bên phải Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 7 Tìm nhị phân (Binary Search) 2 3 6 7 10 12 16 18 [0] [1] [2] [3] [4] [5] [6] [7] [5] [6] [7] 2 3 6 7 10 12 16 18 [0] [1] [2] [3] [4] [5] [6] [7] Tìm thấy Data Structure & Algorithm - Nguyen Tri Tuan - Khoa CNTT ĐH KHTN Tp.HCM Spring 2004 8 4
Binary Search (Minh họa chương trình int BinarySearch(int a[], int n, int key) { int Left = 0, Right = n-1; while (Left