Xem mẫu
- 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
nguon tai.lieu . vn