PHÂN TÍCH
CÁC GI I THU T TÌM KI MẢ Ậ Ế
1
Nội dung
Giải thuật tìm kiếm tuần tự, nhị phân trên danh
sách liên kết
Phân tích các thao tác trên cây tìm kiếm nhị
phân
Phân tích các kỹ thuật băm
Phân tích một vài giải thuật so trùng chuỗi
2
2. Tìm tuyến tính (Linear Seach)
Ý tưởng:
Bắt đầu từ phần tử đầu tiên của danh sách, so sánh lần
lượt từng phần tử của danh sách với giá trị X cần tìm
Nếu có phần tử bằng X thì trả về vị trí tìm thấy, thuật toán
dừng lại (thành công)
Nếu đến cuối danh sách mà không có phần tử nào bằng X,
thuật toán dừng lại (không thành công)
3
Tìm tuyến tính (Linear Seach)
5
Khóa tìm
7 13 5 21 6 2 8 15
0 1234567
V trí = 2ị
Tìm thành công
S l n so sánh: 3ố ầ
4
9
7 13 5 21 6 2 8 15
0 1234567
Không tìm th yấ
S l n so sánh: 8ố ầ
Khóa tìm
2. Tìm tuyến tính (Linear Seach)
5