KHOA CÔNG NGHỆ THÔNG TIN

Bài tập lớn
PHÂN TÍCH ĐÁNH GIÁ THUẬT TOÁN

ĐỀ SỐ 26: Thuật toán tìm kiếm. Cho mảng X có n số nguyên. Hãy xây dựng thuật
toán tìm số lớn thứ hai trong mảng X. Đánh giá độ phức tạp của nó trong trường
hợp xấu nhất.

Giảng viên hướng dẫn
Học viên thực hiện
Mã Sinh viên
Lớp

Hà Nội, 05/2014

: PGS. TS. Đào Thanh Tĩnh
: Dư Quang Trung
: 13870829
: HTTT25B


Mục lục

1. Đặt vấn đề.
Bài toán tìm kiếm là một trong những bài toán phổ biến và có ý nghĩa quan trọng trong cả
cơ sở lý thuyết lẫn ứng dụng thực tiễn của công nghệ thông tin và truyền thông. Quá trình
phát triển của công nghệ khiến ngày càng có nhiều người tiếp cận và sử dụng các thiết bị,
giải pháp công nghệ thông tin. Đi cùng đó là một khối lượng dữ liệu khổng lồ được lưu
trữ, sinh ra hàng ngày. Việc quản lý các cơ sở dữ liệu lớn với các tác vụ cơ bản như: sắp
xếp, truy xuất dữ liệu trở nên hết sức phức tạp. Nhiệm vụ nghiên cứu và triển khai các

vào của chúng. Có ba mô hình dữ liệu đầu vào cơ bản cho một thuật toán tìm kiếm: mảng
(danh sách), cây và đồ thị.
2.1. Tìm kiếm trên mảng (danh sách)
Thuật toán tìm kiếm trên mảng là loại giải thuật tìm kiếm cơ bản nhất. Thuật toán này tìm
kiếm trong một tập hợp một phần tử chứa một khóa nào đó. Thuật toán tìm kiếm trên
mảng đơn giản nhất là tìm kiếm tuyến tính. Thuật toán tìm kiếm tuyến tính kiểm tra từng
phần tử trong danh sách theo thứ tự của danh sách đó. Thuật toán này có độ phức tạp tính
toánO(n), trong đó n là số phần tử trong danh sách. Thuật toán tìm kiếm tuyến tính trên
danh sách có độ phức tạp tính toán lớnnhưng có thể sử dụng trực tiếp cho một danh sách
bất kỳ mà không cần tiền xử lý. Tìm kiếm nhị phân là một thuật toán cao cấp hơn với độ
phức tạp tính toánO(log n). Đối với các danh sách lớn, thuật toán này tốt hơn hẳn tìm
kiếm tuyến tính, nhưng nó đòi hỏi danh sách phải được sắp xếp từ trước và đòi hỏi khả
năng truy nhập ngẫu nhiên vào bất cứ phần tử nào nằm trong mảng. Một thuật toán tìm
kiếm trên mảng hiệu quả khác là thuật toán tìm kiếm nội suy. Độ phức tạp của thuật toán
tìm kiếm nội suy với mảng n phần tử làO(n). Tuy nhiên, trong trường hợp các phần tử của
mảng là số ngẫu nhiên phân bố đều (trường hợp phổ biến nhất), độ phức tạp của thuật
toán có thể đạt chỉ còn O(loglogN).
Bảng băm (hash table) cũng được dùng cho tìm kiếm trên danh sách. Thuật toán này đòi
hỏi thời gian hằng số trong trường hợp trung bình, nhưng lại cần nhiều không gian bộ
nhớ và độ phức tạp thuật toánO(n) cho trường hợp xấu nhất. Một phương pháp tìm kiếm
khác dựa trên các cấu trúc dữ liệu chuyên biệt sử dụng cây tìm kiếm nhị phân cân bằng

3


và độ phức tạp thuật toánO(log n); các giải thuật loại này có thể coi là mở rộng của thuật
toán tìm kiếm nhị phân để cho phép chèn và xóa nhanh.
Đa số các giải thuật tìm kiếm trên mảng như tìm kiếm tuyến tính, tìm kiếm nhị phân, và
cây tìm kiếm nhị phân cân bằng đều có thể được mở rộng để tìm tất cả các giá trị nhỏ hơn
hoặc lớn hơn một khóa cho trước.

cây khung nhỏ nhất, bài toán tìm đường đi ngắn nhất giữa hai đỉnh. Các thuật toán phổ
biến được sử dụng như thuật toán Prim, thuật toán Kruskal tìm cây khung nhỏ nhất, thuật
toán Dijktra tìm đường đi ngắn nhất.

3. Bài toán: Cho mảng X có n số nguyên. Hãy xây dựng thuật toán tìm số lớn thứ
hai trong mảng X. Đánh giá độ phức tạp của nó trong trường hợp xấu nhất.
Để có thể triển khai được thuật toán tìm số lớn thứ hai trong mảng, cần phải có dữ liệu
đầu vào. Dữ liệu đầu vào có thể là dữ liệu thực tế. Trong bài tập lớn này, dữ liệu đầu vào
được sinh ra tự động nhờ các thuật toán mô phỏng dữ liệu đầu vào bằng máy tính.
3.1. Thuật toán mô phỏng dữ liệu đầu vào
Dữ liệu đầu vào của bài toán là một mảng có n số nguyên. Mảng số này có thể có các
trường hợp sau:
Mảng số có trật tự
 Mảng tăng/không giảm.
 Mảng giảm/ không tăng.
• Mảng số ngẫu nhiên
 Số ngẫu nhiên có xác suất xuất hiện tuân theo một hàm phân bố nào đó.
•

Các thuật toán để mô phỏng dữ liệu đầu vào như sau:
a. Mảng có trật tự
Ý tưởng thuật toán: tạo một số ngẫu nhiên làm phần tử đầu tiên của dãy. Sinh ra các số
tiếp theo bằng cách cộng thêm vào số ngẫu nhiên ban đầu một giá trị ngẫu nhiên.
Đầu vào: Số phần tử n của dãy cần tạo
Đầu ra: Dãy tăng/không giảm có n phần tử.
Trình bày thuật toán bằng giả mã lệnh:
void generateIncreasingArray()
{
int a[1000];// ví dụ mảng có 1000 phần tử;
for (int i = 0;i
Các giá trị đặc trưng của từng hàm phân bố (ví dụ giá trị trung bình và phương sai
của phân bố Gauss, giá trị trung bình của phân bố Poisson…). Để các dãy số đầu
vào cho thuật toán tìm kiếm có tính thống nhất, các tham số của hàm phân bố sẽ
được lựa chọn sao cho các số ngẫu nhiên sinh ra có giá trị tập trung trong khoảng
[0,1000]. Tham số được lựa chọn tương ứng cho các hàm phân bố là:
 Phân bố đều: mean = 500;
 Phân bố Gauss: mean = 500, standard deviation = 300
 Phân bố Poisson: mean = 500;
 Phân bố Exponential: rate = 500;

Đầu ra: Dãy ngẫu nhiên có n phần tử tuân theo phân bố xác suất.
Trình bày thuật toán bằng giả mã lệnh:
//Tạo số ngẫu nhiên theo phân bố chuẩn
int Uniform(float mean)
6


{

int R;
R = (int)((float)rand()/(float)(RAND_MAX));

return (int)(2*mean*R);
}
//Tạo số ngẫu nhiên theo phân bố Exponential
int Exponential(float mean)
{
int R;
R = (int)((float)rand()/(float)(RAND_MAX));
return (int)(-mean*log(R));


7


Hình 1. Đồ thị phân bố mật độ xác suất xuất hiện số ngẫu nhiên sinh theo các hàm phân
bố đều, phân bố exponential, phân bố gauss, phân bố poisson (từ trên xuống dưới).

3.2. Các thuật toán tìm kiếm số lớn thứ hai trong mảng.
3.2.1. Tìm kiếm tuyến tính
Tìm kiếm tuyến tính (hay tìm kiếm tuần tự) là thuật toán tìm kiếm phổ biến nhất và gần
như là thuật toán tìm kiếm bắt buộc khi thực hiện việc tìm kiếm trên các dãy ngẫu nhiên
không có trật tự, hoặc các dãy không có khả năng truy cập vào phần tử bất kì. Thuật toán
tìm kiếm tuyến tính không yêu cầu mảng (dãy) dữ liệu đầu vào phải được sắp xếp hoặc
tiền xử lý.
Ý tưởng thuật toán.
Lần lượt so sánh phần tử cần tìm x với phần tử thứ nhất, thứ hai, thứ ba,… của dãy số cho
đến phần tử cuối cùng của dãy. Lưu lại địa chỉ (vị trí) các phần tử thỏa mãn (nếu tìm
được).
Đầu vào:
•
•
•

x: Phần tử cần tìm (phần tử lớn thứ hai)
n: Số phần tử của mảng (dãy) đầu vào.
A[n]: Mảng chứa các phần tử.

Đầu ra :
•


}

1 phép gán
1 phép so sánh
1 phép gán

Độ phức tạp tính toán:
•

Cần tiến hành n bước duyệt. Với mỗi bước duyệt cần 1 phép so sánh trong trường

•

hợp tốt nhất và 3 phép so sánh liên tiếp trong trường hợp xấu nhất. Khi phép so
sánh trả về đúng, cần thực hiện 1 phép gán. Vậy trong trường hợp xấu, với mỗi lần
duyệt cần thực hiện 4 phép toán gồm 3 phép so sánh và 1 phép gán. Tổng số phép
toán trong trường hợp xấu nhất là 4n phép toán.
Do duyệt tuần tự, số lượng các phần tử thỏa mãn yêu cầu tìm kiếm có thể là bất kì,

•

do vậy trong hầu hết mọi trường hợp đều cần duyệt đến cuối danh sách, nên độ
phức tạp tính toán trung bình phần lớn bằng độ phức tạp tính toán trong trường
hợp xấu nhất.
Độ phức tạp tính toán O(n).

3.2.2. Sắp xếp mảng ngẫu nhiên và tìm kiếm duyệt từ một phía có điều kiện.
Thuật toán tìm kiếm số lớn thứ hai theo chỉ số dựa trên việc sử dụng các thuật toán sắp
xếp để đưa một mảng ngẫu nhiên về một mảng có trật tự. Công việc của thuật toán này
bao gồm hai bước: sắp xếp mảng ngẫu nhiên đã cho và tìm kiếm dựa trên chỉ số của phần

//Truong hop day khong giam
void index_search(n, array A) //Array A la day da sap xep khong giam
{
int max = A[n-1];
int second_max;
while ((max == A[n-1])&&(n>1))
n--;
tối đa n lần duyệt
second_max = A[n-1];
printf(“Second_max = %d”,second_max);
}

Độ phức tạp tính toán:
•

Với dãy tăng, có thể đơn giản xác định ngay phần tử lớn thứ hai là phần tử A[n-2].

•

Độ phức tạp tính toán là O(1).
Với dãy không giảm, do có thể có nhiều hơn một số lớn nhất, nên để tìm phần tử
lớn thứ hai cần duyệt từ cuối dãy để tìm ra phần tử lớn thứ hai. Sẽ có tối đa n lần
duyệt (ứng với mảng n phần tử giống hệt nhau). Độ phức tạp tính toán trong
trường hợp xấu nhất là O(n).

Độ phức tạp tính toán vào thời gian tìm kiếm của thuật toán tìm kiếm nhị phân nhỏ hơn
nhiều so với tìm kiếm tuần tự. Tuy nhiên, để đạt được độ phức tạp và thời gian tìm kiếm
này, thuật toán tím kiếm nhị phân chỉ làm việc trên các mảng đã được sắp xếp. Do vậy độ
phức tạp tính toán tổng quát của thuật toán tìm kiếm nhị phân còn gồm cả độ phức tạp
tính toán của thuật toán sắp xếp được lựa chọn để sắp xếp mảng dữ liệu đầu vào. Các

đổi chỗ

Sắp xếp nổi bọt

O(n)

O(n2)

O(n2)

Sắp xếp nhanh

O(nlogn)

O(nlogn)

O(n2)

Sắp xếp trộn

O(nlogn)

O(nlogn)

O(nlogn)

Sắp xếp vun đống

O(nlogn)


STT

Tình huống phức tạp

Hướng giải quyết

Ưu – nhược điểm

1

Dữ liệu đầu vào quá lớn, vượt quá - Không load hết - Thời gian tìm kiếm
khỏi khả năng quản lý bộ nhớ của toàn bộ dữ liệu vào sẽ tăng lên rất nhiều
hệ điều hành/ngôn ngữ lập bộ nhớ mà load từng do phải truy cập vào
11


trình/trình dịch. Ví dụ các cơ sở dữ
liệu về thông tin dân số, quy mô dữ
liệu có thể lên đến hàng chục, hàng
trăm triệu mẫu dữ liệu.

đoạn dữ liệu vào bộ
nhớ, phần dữ liệu
còn lại vẫn nằm trên
đĩa cứng, hoặc tiến
hành tìm kiếm trực
tiếp trên đĩa cứng.

đĩa cứng, vốn có tốc
độ truy cập chậm


3

- Hướng giải quyết
không khả thi trong
một số trường hợp
- Quản lý, cấp phát phải truy cập đến
bộ nhớ động (dùng toàn bộ dữ liệu một
con trỏ, malloc…)
cách gần như tức
thời, ví dụ trong các
thuật toán sắp xếp.

Thời gian tìm kiếm/sắp xếp quá
lâu, lên đến hàng giờ, ngày -> có
thể gặp các rủi ro như máy tính bị
crash, mất điện,etc..khiến cho toàn
bộ công việc đã thực hiện được bị
mất, phải tiến hành lại từ đầu…

- Xây dựng thuật
toán theo hướng có
thể “phân mảnh
hoá” quá trình tìm
kiếm.
- Lưu dữ liệu đầu ra
của bước tìm kiếm
trước để làm đầu
vào bổ sung của
bước tìm kiếm sau.


10000

100000

200000

500000

1M

2M

5M

Uniform

17

35

299

606

1553

3035

6498


1642

3025

6103

14999

Poisson

8

53

53

643

1496

3021

6094

15044

Bảng 3. Thời gian tìm kiếm sử dụng thuật toán tìm kiếm tuần tự

Từ đồ thị biểu diễn thời gian tìm kiếm phần tử lớn thứ hai trong mảng theo số lượng phần


Uniform

123

1327

25684

76026

391319

1371710

5366560

Exponential

156

1532

46070

152765

834429

3260902


4321954

12543546

Bảng 4. Thời gian tìm kiếm sử dụng thuật toán sắp xếp nhanh

Từ đồ thị biểu diễn thời gian sắp xếp mảng và tìm kiếm phần tử lớn thứ hai trong mảng
sử dụng thuật toán sắp xếp nhanh, ta thấy:
Thời gian tính toán của thuật toán khá tương đồng với công thức Độ phức tạp tính
toán trung bình của thuật toán là O(nlogn).
• Thuật toán sắp xếp nhanh hơn trên các mô hình dữ liệu ngẫu nhiên có phân bố
đều và phân bố Gauss, chậm hơn trên các mô hình dữ liệu ngẫu nhiên có phân bố
Exponential và phân bố Poisson, đặc biệt là khi số lượng mẫu dữ liệu trở nên rất
lớn.
•

Đơn vị:
microsecond

1000

10000

100000

200000

500000


293489

594197

1178007

Gauss

257

3387

56779

119087

290577

592123

1188633

14


Poisson

218

2212

• Thuật toán tìm kiếm tuần tự. Độ phức tạp trong trường hợp xấu nhất: O(n).
• Thuật toán tìm kiếm duyệt từ một phía có điều kiện của mảng đã sắp xếp. Độ phức
tạp của thuật toán phụ thuộc vào độ phức tạp của thuật toán sắp xếp. Sử dụng thuật
toán sắp xếp nhanh, độ phức tạp trong trường hợp xấu nhất là O(n2), sử dụng thuật
toán sắp xếp trộn, độ phức tạp trong trường hợp xấu nhất là O(nlogn).
Các kết luận rút ra từ bài tập lớn.
• Kiểm chứng được các công thức đánh giá độ phức tạp của hai thuật toán nói trên
bằng thử nghiệm thực tế.
• Thuật toán tìm kiếm tuần tự cho thời gian tìm kiếm phần tử lớn thứ hai nhanh hơn
so với thuật toán yêu cầu sắp xếp.
• Nếu có thể tiến hành thuật toán sắp xếp vào khoảng thời gian “rảnh” trước khi có
yêu cầu tìm kiếm, thì thời gian tìm kiếm trên mảng đã sắp xếp nhanh hơn nhiều so
với tìm kiếm tuần tự.
• Thuật toán sắp xếp trộn chậm hơn thuật toán sắp xếp nhanh với các mảng có ít
phần tử (từ 100000 phần tử trở xuống), và nhanh hơn đáng kể thuật toán sắp xếp
15


nhanh với các mảng có từ nhiều đến rất nhiều phần tử (từ vài trăm nghìn đến vài
triệu phần tử).
• Các tình huống phức tạp có thể xảy ra khi tính toán là: khối lượng dữ liệu vào quá
lớn, gây ra các sự cố về tràn bộ nhớ, cấp phát bộ nhớ. Chương trình giải quyết tình
huống phức tạp này bằng cách áp dụng các kỹ thuật cấp phát bộ nhớ động, ghi dữ
liệu ra file và đọc tuần tự từng phần vào bộ nhớ.
Nhóm tác giả thực hiện bài tập lớn xin chân thành cảm ơn PGS.TS. Đào Thanh Tĩnh đã
tận tình giảng dạy và hướng dẫn nhóm tác giả trong suốt quá trình nghiên cứu môn học
Phân tích đánh giá thuật toán cũng như quá trình nghiên cứu, thực hiện bài tập lớn.

16