Bài giảng Cấu trúc dữ liệu - Chương 13: Tìm kiếm trình bày về định nghĩa giải thuật tìm kiếm, phân loại tìm kiếm, giải thuật, cài đặt và độ phức tạp của các loại tìm kiếm. Hy vọng đây là tài liệu tham khảo hữu ích cho bạn.
AMBIENT/
Chủ đề:
Nội dung Text: Bài giảng Cấu trúc dữ liệu: Chương 13 - Nguyễn Xuân Vinh
- GV: NGUYỄN XUÂN VINH
CẤU TRÚC DỮ LIỆU
DATA STRUCTURES
[214331]
TÌM KIẾM
MÔN: CẤU TRÚC DỮ LIỆU
Teacher: Nguyễn Xuân Vinh
6/12/14
Email:
nguyenxuanvinh@hcmuaf.edu.
/XX
vn
1
- GV: NGUYỄN XUÂN VINH
Định nghĩa
•
Giải thuật tìm kiếm là một thuật toán trả về kết quả là một lời
giải cho bài toán đó.
•
Trong giải thuật tìm kiếm người ta thường cân nhắc giữa các lời
giải có thể và tìm ra lời giải tối ưu nhất.
•
Không gian tìm kiếm: tập hợp các lời giải có thể đối với 1 bài
MÔN: CẤU TRÚC DỮ LIỆU
toán.
6/12/14
/XX
2
- GV: NGUYỄN XUÂN VINH
Phân loại tìm kiếm
•
Tìm kiếm không có thông tin
–
Tìm kiếm trên danh sách
–
TÌm kiếm trên cây
–
Tìm kiếm trên đồ thị
MÔN: CẤU TRÚC DỮ LIỆU
•
TÌm kiếm có thông tin
•
Tìm kiếm đối kháng
•
Thỏa mãn ràng buộc
6/12/14
/XX
3
- GV: NGUYỄN XUÂN VINH
Tìm kiếm không có thông tin
•
Một giải thuật không tính đến bản chất cụ thể của bài toán.
•
Ưu điểm:
–
Có thể được sử dụng cho nhiều bài toán.
•
Nhược điểm:
MÔN: CẤU TRÚC DỮ LIỆU
–
Không gian tìm kiếm rất lớn.
–
Thời gian tìm kiếm lâu.
6/12/14
/XX
4
- GV: NGUYỄN XUÂN VINH
Tìm kiếm trên danh sách
•
Tìm một khóa nào đó trong 1 tập hợp các phần tử nào đó.
•
Các thuật toán:
–
Tìm kiếm tuyến tính – linear search
–
Tìm kiếm nhị phân – binary search
–
Tìm kiếm nội suy – interpolation search
MÔN: CẤU TRÚC DỮ LIỆU
–
Fibonaccian search
–
Jump search
–
Secant search
–
Bảng băm – hashtable
–
Cây tìm kiếm nhị phân cân bằng – self-balancing binary search tree
6/12/14
/XX
5
- GV: NGUYỄN XUÂN VINH
Tìm kiếm tuyến tính – linear search
•
Ý tưởng của thuật toán: Thuật toán tiến hành kiểm tra từng phần
tử trong danh sách theo thứ tự của danh sách đó.
•
Ưu điểm:
–
Đơn giản, dễ cài đặt
–
Có thể áp dụng cho 1 danh sách bất kỳ mà không cần tiền xử
MÔN: CẤU TRÚC DỮ LIỆU
lý.
•
Nhược điểm:
–
Thời gian chạy lớn:
• Trường hợp trung bình và xấu nhất O(n).
• Trường hợp tốt nhất O(1).
6/12/14
/XX
6
- GV: NGUYỄN XUÂN VINH
Tìm kiếm tuyến tính – linear search
•
http://www.cosc.canterbury.ac.nz/mukundan/dsal/LSearch.html
•
Minh họa tìm x =10
10
MÔN: CẤU TRÚC DỮ LIỆU
Đã tìm
7 5 12 41 10 32 13 9 15 3 thấy tại
1 2 3 4 5 6 7 8 9 10 vị trí 5
•
Minh họa tìm x = 25
25
Đã hết
7 5 12 41 10 32 13 9 15 3
mảng
1 2 3 4 5 6 7 8 9 10
6/12/14
7
/XX
7
- GV: NGUYỄN XUÂN VINH
Giải thuật
•
Bước 1: i = 1 //bắt đầu từ phần tử đầu tiên của dãy.
•
Bước 2: so sánh a[i] với x, có 2 khả năng:
–
a[i] = x: tìm thấy, dừng thuật toán.
–
a[i] != x: sang bước 3.
MÔN: CẤU TRÚC DỮ LIỆU
•
Bước 3:
–
i = i+1 //xét phần tử kế tiếp trong mảng
–
Nếu i > n: hết mảng, không tìm thấy, dừng.
–
Ngược lại: lặp lại bước 2.
6/12/14
/XX
8
- 9 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
Cài đặt
- GV: NGUYỄN XUÂN VINH
Độ phức tạp
•
Độ phức tạp trong thuật toán này chính là số lần thực hiện các
phép so sánh.
•
Mỗi bước của vòng lặp cần 2 phép so sánh:
–
Đã hết danh sách chưa.
Có bằng phần tử cần tìm không
MÔN: CẤU TRÚC DỮ LIỆU
–
•
Do đó tại bước thứ i đã có 2i phép so sánh.
•
Trong trường hợp xấu nhất ta có 2n phép so sánh
•
độ phức tạp O(n)
6/12/14
/XX
10
- GV: NGUYỄN XUÂN VINH
Tìm kiếm nhị phân – binary search
•
Ý tưởng của thuật toán: giả sử danh sách đã được sắp xếp, ta
tiến hành chọn một phần tử ở giữa danh sách (middle), sau đó so
sánh phàn tử cần tìm kiếm (target) và phần tử middle.
–
Nếu target=middle: đã tìm thấy, kết thúc thuật toán.
–
Nếu target>middle: tiếp tục tìm kiếm nửa bên phải của danh
MÔN: CẤU TRÚC DỮ LIỆU
sách cũ.
–
Nếu target
- GV: NGUYỄN XUÂN VINH
Tìm kiếm nhị phân – binary search
•
Ưu điểm:
–
Thời gian chạy nhanh:
• Trường hợp tốt nhất O(1)
• Trường hợp trung bình và xấu nhất O(logn).
MÔN: CẤU TRÚC DỮ LIỆU
•
Nhược điểm:
–
Danh sách phải được sắp xếp trước.
–
Danh sách phải có khả năng truy xuất ngẫu nhiên.
6/12/14
/XX
12
- GV: NGUYỄN XUÂN VINH
Tìm kiếm nhị phân – binary search
•
http://www.cosc.canterbury.ac.nz/mukundan/dsal/BSearch.html
MÔN: CẤU TRÚC DỮ LIỆU
6/12/14
/XX
13
- GV: NGUYỄN XUÂN VINH
Tìm kiếm nhị phân – binary search
Minh họa tìm x = 41
MÔN: CẤU TRÚC DỮ LIỆU
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
6/12/14
m
14
/XX
14
- GV: NGUYỄN XUÂN VINH
Tìm kiếm nhị phân – binary search
Minh họa tìm x = 45
x x x x
MÔN: CẤU TRÚC DỮ LIỆU
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
6/12/14
15
m
/XX
15
- GV: NGUYỄN XUÂN VINH
Giải thuật
•
Bước 1: left = 1, right = N //tì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.
MÔN: CẤU TRÚC DỮ LIỆU
• a[mid] > x //tìm tiếp trong dãy con aleft …amid-1
right = mid – 1;
• a[mid] < x //tìm tiếp trong dãy con amid+1 …aright
left = mid+1
•
Bước 3:
–
left
- 17 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
Cài đặt
- 18 /XX 6/12/14 MÔN: CẤU TRÚC DỮ LIỆU GV: NGUYỄN XUÂN VINH
So sánh giữa TKTT & TKNP
- GV: NGUYỄN XUÂN VINH
Tìm kiếm nhị phân – binary search
•
Ý tưởng: là giải thuật tìm kiếm trên danh sách đã được sắp xếp
bằng cách ước lượng vị trí tiếp theo để kiểm tra bằng phép nội
suy tuyến tính của khóa và giá trị của phần tử cuối cùng của danh
sách.
–
Tức là sử dụng các vị trí đã biết để đoán ra các vị trí có thể.
MÔN: CẤU TRÚC DỮ LIỆU
•
Ưu điểm:
–
Thời gian chạy nhanh:
• Trung bình: O(log log n)
• Trường hợp xấu nhất: O(n)
6/12/14
/XX
19
- GV: NGUYỄN XUÂN VINH
Giải thuật
•
Bước 1: chọn l = 0, r = N-1
•
Bước 2:
–
m = l + (x – a[l])*(r-l)/(a[r]-a[l]) Hàm nội suy
–
Tiến hành so sánh, có 3 trường hợp xảy ra:
• x = a[m]: Tìm thấy, dừng.
MÔN: CẤU TRÚC DỮ LIỆU
• x < a[m]: đặt r = m-1
• x > a[m]: đặt l = m + 1
•
Bước 3:
–
Nếu xa[r] m>r hay m
Thêm vào BST
Báo xấu
Download
Vui lòng tải xuống để xem tài liệu đầy đủ
