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

while ((i<N) && (a[i]!=key
)) i++;
if(i==N)
return -1;// tìm hết
mảng nhưng không
có khóa key
else
return i;// a[i] là phần
tử có khoá key
}
Mỗi lần lặp của vòng lặp while phải tiến thành kiểm tra 2 điều kiện (i<N) - điều
kiện biên của mảng - và (a[i]!=x )- điều kiện kiểm tra chính.
Tìm tuyến tính (Linear Seach)

int LinearSearch(int a[],int N,int key) //Dùng pp lính canh

{ int i=0; // mảng gồm N phần tử từ a[0] a[N-1]

a[N] = key; // thêm phần tử thứ N+1

while (a[i]!=x ) i++;

if (i==N)

return -1; // tìm hết mảng nhưng không có x

else

return i; // tìm thấy x tại vị trí i



Nếu bằng, tìm kiếm dừng lại (thành công)

Nếu X lớn hơn thì tiếp tục tìm kiếm ở phần danh sách bên
phải phần tử giữa

Nếu X nhỏ hơn thì tiếp tục tìm kiếm ở phần danh sách bên trái
phần tử giữa
9
Tìm nhị phân (Binary Seach)
10
Khóa tìm
2 5 8 10
12
13 15 18 21 24
0 1 2 3 4 5 6 7 8 9
left rightmid
Vi trí = 3
Tìm thấy
Số lần so sánh: 4
Khóa cần tìm nhỏ hơn
Khóa cần tìm lớn hơn
Khóa cần tìm bằng
10
Tìm nhị phân (Binary Seach)
void BSearch (int list[], int n, int key)
{
int left, right, mid, flag = 0;
left = 0; right = n-1;
while (left <= right) {

Đệ quy
12
Tìm nhị phân (Binary Seach)

Phân tích, đánh giá thuật toán:

Vậy giải thuật tìm nhị phân có độ phức tạp tính toán
cấp n: T(n) = O(log
2
n)
Trường hợp Số lần so sánh Giải thích
Tốt nhất 1 Phần tử giữa của mảng có giá trị x
Xấu nhất
log
2
n
Không có x trong mảng
Trung bình
log
2
(n/2)
Giả sử xác suất các phần tử trong
mảng nhận giá trị x là như nhau
13
Tìm nhị phân (Binary Seach)

Giải thuật tìm nhị phân dựa vào quan hệ giá trị của các phần tử
mảng để định hướng trong quá trình tìm kiếm, do vậy chỉ áp
dụng được cho những dãy đã có thứ tự.


mảng các số nguyên.
15
Tìm nhị phân (Binary Seach)_BT
Bài tập THỰC HÀNH :
1. Cài đặt các thuật toán tìm kiếm đã trình bày. Thể hiện
trực quan các thao tác của thuật toán. Tính thời gian
thực hiện của mỗi thuật toán.
2. Hãy viết hàm tìm tất cả các số nguyên tố nằm trong
mảng một chiều a có n phần tử.
3. Hãy viết hàm tìm dãy con tăng dài nhất của mảng một
chiều a có n phần tử (dãy con là một dãy liên tiếp các
phần của a).
4. Cài đặt thuật toán tìm phần tử trung vị (median) của một
dãy số.
16
Tìm kiếm trên danh sách liên kết
17

Tìm kiếm một phần tử có khóa x
Node* Search (List l, int x)
{
Node* p = l.pHead;
while (p!=NULL) {
if (p->data==x)
return p;
p=p->pNext;
}
return NULL;
}
• Tìm kiếm mất tối đa

13
13
37
37
59
59
108
108
15
15
23
23
40
40
55
55
71
71
Binary Search Tree – Khai báo
20

Khai báo cấu trúc cây nhị phân tìm kiếm:

Để quản lý cây nhị phân tìm kiếm chỉ cần quản lý
địa chỉ nút gốc:
Tree root;
struct TNode
{
DataType data;
TNode *pLeft, *pRight;

37
29
35
32
50
41
Duyệt postorder(LRN): 1 5 6 3 13 12 20 18 10 32 35 29 41 50 37
25
Duyệt sau trên CNPTK (LRN)
Binary Search Tree – Duyệt cây
23
25
10
3
1 6
5
18
12 20
13
37
29
35
32
50
41
Duyệt preorder(NLR): 25 10 3 1 6 5 18 12 13 20 37 29 35 32 50 41
Duyệt trước trên CNPTK(NLR)
Thuật Toán Inorder Traversal
Inorder-Tree-Walk (x)
1. if x

3
1 6
5
18
12 20
13
37
29
35
32
50
41
Tìm kiếm 13
Khác nhau
Giống nhauNode gốc nhỏ hơnNode gốc lớn hơn
Tìm thấy
Số node duyệt: 5
Tìm kiếm trên CNPTK