Tìm kiếm là thao tác rất phổ biến trong cuộc
sống hàng ngày.
Các loại tìm kiếm:
Tìm kiếm tuần tự (Sequential/ Linear Search)
Tìm kiếm nhị phân (Binary Search)
Mục tiêu:
Tìm hiểu về 2 giải thuật tìm kiếm cơ bản.
Phân tích thuật toán để lựa chọn thuật toán
phù hợp với dữ liệu đầu vào
28 trang
|
Chia sẻ: thuychi16
| Lượt xem: 905
| Lượt tải: 0
Bạn đang xem trước
20 trang
tài liệu Cấu trúc dữ liệu và giải thuật – Các thuật toán tìm kiếm và sắp xếp cơ bản, để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
CẤU TRÚC DỮ LIỆU VÀ GIẢI THUẬT
CÁC THUẬT TOÁN TÌM KIẾM
VÀ SẮP XẾP CƠ BẢN
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
1
Nội dung trình bày
Giới thiệu các giải thuật tìm kiếm
Tìm kiếm tuần tự
Tìm kiếm nhị phân
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
2
Đánh giá và tổng kết
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
3
Tìm kiếm là thao tác rất phổ biến trong cuộc
sống hàng ngày.
Các loại tìm kiếm:
Tìm kiếm tuần tự (Sequential/ Linear Search)
Tìm kiếm nhị phân (Binary Search)
Mục tiêu:
Tìm hiểu về 2 giải thuật tìm kiếm cơ bản.
Phân tích thuật toán để lựa chọn thuật toán
phù hợp với dữ liệu đầu vào.
1. Giới thiệu thuật toán tìm kiếm
2.1. Tìm kiếm tuần tự – Vét cạn
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
4
Ý tưởng: So sánh x lần lượt với các phần tử
của mảng A cho đến khi gặp được phần tử có
giá trị x cần tìm, hoặc đã tìm đến hết mảng
mà không thấy x.
Minh họa:
25 7 3 12 27 5 9 8 61
x = 27
27 27 27 27 27
Có x trong
mảng
8
8 8 8 8 8 28 28 28 28
Không tìm thấy x
trong mảng
28
2.1. Tìm kiếm tuần tự – Vét cạn
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
5
Input:
Mảng A.
n phần tử.
Giá trị x cần tìm
Output:
Nếu x xuất hiện trong A, trả về 1.
Ngược lại, trả về 0.
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
6
Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0
Bước 2: so sánh i và n
Nếu chưa hết mảng (i<n), sang bước 3;
Nếu đã hết mảng (i>=n), kết thúc.Trả về 0.
Bước 3: So sánh giá trị A[i] với x
Nếu A[i] bằng x: kết thúc. Trả về 1.
Nếu A[i] khác x, tăng i thêm 1 và quay lại
bước 2.
2.1. Tìm kiếm tuần tự – Vét cạn
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
7
Bắt đầu
Nhập A, n, x
i = 0
i>=n
A[i] = x
i = i+1
Kết
thúc
Lưu đồ
thuật toán
Đ
S
S
Đ
2.1. Tìm kiếm tuần tự – Vét cạn
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
8
Mỗi vòng lặp, có 2 điều kiện cần kiểm tra:
Kiểm tra đã duyệt hết mảng? (bước 2)
Kiểm tra phần tử hiện tại có bằng x?(bước 3)
Số phép so sánh trung bình:
2(1+2+3++n)/n = n+1
Số phép so sánh tăng/giảm tuyến tính theo số
phần tử.
2.1. Tìm kiếm tuần tự – Vét cạn
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
9
Độ phức tạp của thuật toán:
Tốt nhất: O(1)
Trung bình: O(n)
Xấu nhất: O(n)
2.1. Tìm kiếm tuần tự – Vét cạn
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
10
Có thể bỏ qua việc kiểm tra điều kiện cuối
mảng bằng cách dùng “lính canh”.
Lính canh là phần tử có giá trị bằng với
phần tử cần tìm và được đặt ở cuối mảng.
2.2. Tìm kiếm tuần tự – Lính canh
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
11
Ví dụ: A = {25, 6, 18, 4}; x = 7
25 6 18 4 7
x=7
25 6 18 4 7
25 6 18 4 7 25 6 18 4 7
x=7
x=7
x=7
x=7
25 6 18 4 7
i = 4
(i>n)
(1) (2)
(3) (4)
(5)
2.2. Tìm kiếm tuần tự – Lính canh
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
12
Bước 1: Bắt đầu từ phần tử đầu tiên: i = 0
Bước 2: So sánh giá trị A[i] với giá trị x
Nếu A[i] khác x, tăng i thêm 1 và quay lại bước 2.
Nếu A[i] bằng x:
• Nếu i<n: kết thúc chương trình và trả về 1
• Nếu i>=n: kết thúc, trả về 0.
2.2. Tìm kiếm tuần tự – Lính canh
Task
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
13
Task 1: Cài đặt thuật toán tìm kiếm theo
cách vét cạn và sử dụng lính canh.
Task 2: Xây dựng thuật toán và cài đặt
chương trình tìm những vị trí mà x xuất hiện
trong mảng cho trước.
Task 3: Xây dựng thuật toán và cài đặt
chương trình tìm xem trong mảng cho trước
có phần tử nào là số chẵn hay không?
3. Tìm kiếm nhị phân
(Binary Search)
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
14
Thuật toán tìm kiếm nhị phân
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
15
Với dãy A được sắp xếp tuần tự (tăng/giảm)
thì độ phức tạp của thuật toán tìm kiếm tuần
tự không đổi.
Tận dụng thông tin của mảng đã được sắp
xếp để giới hạn vùng tìm kiếm của giá trị cần
tìm trong mảng.
Thuật toán tìm kiếm nhị phân.
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
16
Thuật toán tìm kiếm nhị phân
Input:
Mảng A với n phần tử đã được sắp xếp.
Giá trị x cần tìm.
Output:
Nếu x xuất hiện trong A, trả về 1.
Ngược lại, trả về 0.
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
17
Ý tưởng:
So sánh x với giá trị của phần tử chính giữa của
mảng A.
Nếu x là phần tử chính giữa thì dừng.
Nếu không, xác định xem x thuộc nửa trái
hay nửa phải của phần tử chính giữa.
Lặp lại 2 bước trên với nửa đã được xác định.
Thuật toán tìm kiếm nhị phân
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
18
Bước 1: left = 0; right = n-1;
Bước 2: mid = (left + right)/2;
So sánh A[mid] với x có 3 khả năng:
A[mid] = x: Tìm thấy. Dừng.
A[mid] > x: right = mid – 1;
A[mid] < x: left = mid + 1;
Bước 3: Nếu left <= right: lặp lại Bước 2.
Ngược lại: Dừng.
Thuật toán tìm kiếm nhị phân
Index 0 1 2 3 4 5 6
A[i] 4 8 15 17 32 59 72
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
19
Minh họa:
A[] = {4, 8, 15, 17, 32, 59, 72}, x = 8.
Thuật toán tìm kiếm nhị phân
x<A[3]
x=A[1]
Đã tìm thấy x
trong A, kết thúc
Lần 1 right
mid
left
Lần 2
=(0+6)/2=3 2 1i
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
20
Minh họa:
A[] = {4, 8, 15, 17, 32, 59, 72},
Index 0 1 2 3 4 5 6
A[i] 4 8 15 17 32 59 72
Thuật toán tìm kiếm nhị phân
x>A[3]
left right l f
mid
x>A[5]
left right
x=A[6] Tìm thấy x trong
A, kết thúc
Lần 1
Lần 2
Lần 3
mid=(0+6)/2=3 4 56 6
x = 72 3
> Không tìm hấy x
trong A, kết thúc
left>right
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
21
Phân tích thuật toán:
Mỗi lần lặp thì chiều dài của mảng con giảm
đi ½ so với chiều dài mảng trước đó.
Chia mảng A đến khi còn 1 phần tử:
(((((n/2)/2)/2))/2) = n/2k
n/2k =1; n = 2k ; log2n= log2n; k = log2n
Số lần thực hiện vòng lặp while khoảng k
lần, mỗi vòng lặp thực hiện 1 phép so sánh.
Thuật toán tìm kiếm nhị phân
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
22
Phân tích thuật toán:
Trường hợp tốt nhất: k = 1 x là phần tử
chính giữa của mảng.
Trường hợp xấu nhất: k = log2n x không
thuộc mảng hoặc x là phần tử thuộc biên của
mảng.
Số phép so sánh tăng theo hàm logarit.
Thuật toán tìm kiếm nhị phân
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
23
Độ phức tạp của tìm kiếm nhị phân:
Trường hợp tốt nhất: O(1)
Trường hợp trung bình: O(log2n/2)
Trường hợp xấu nhất: O(log2n)
Thuật toán tìm kiếm nhị phân
So sánh hiệu suất
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
24
So sánh trường hợp xấu nhất của 2 thuật
toán tìm kiếm:
Kích thước
mảng
Trường hợp xấu nhất
Tuần tự Nhị phân
100.000 100.000 16
200.000 200.000 17
400.000 400.000 18
800.000 800.000 19
1.600.000 1.600.000 20
4. Tổng kết
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
25
Thuật toán tuần tự:
Tìm kiếm cho đến khi tìm thấy giá trị cần tìm
hoặc hết mảng.
Hiệu suất của tìm kiếm tuần tự trong trường hợp
xấu nhất là 1 hàm tuyến tính theo số phần tử của
mảng.
Tìm kiếm nhị phân:
Dùng kết quả của phép so sánh để thu hẹp vùng
tìm kiếm kế tiếp.
Hiệu suất của tìm kiếm nhị phân là một hàm
logarit theo số phần tử của mảng.
LinearSearch
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
26
bool LinearSearch(int a[], int n, int x)
{
int kq = true;
for(int i=0; i<n;i++)
{
if(a[i]==x)
return kq;
kq = false;
}
return kq;
}
BinarySearch
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
27
Bool BinarySearch(int a[], int n, int x)
{
int left=0, right=n-1,mid;
bool kq=true;
do{
mid=(left+right)/2;
if(x==a[mid])
return kq;
else if(x<a[mid])
right=mid-1;
else left=mid+1;
} while(left<right);
return kq=false;
}
8/27/2015 Các thuật toán tìm kiếm và sắp xếp cơ bản
28
1. Sử dụng thuật toán tìm kiếm tuần tự trên mảng 1
chiều, cài đặt các hàm xử lý các yêu cầu sau:
– Đếm số lượng của x có trong mảng.
– Xuất ra các vị trí của x trong mảng.
2. Sử dụng thuật toán tìm kiếm nhị phân với mảng bất
kỳ.
