Ôn tập các thuật toán tìm kiếm¶

Thuật toán tìm kiếm được sử dụng để tìm kiếm một hoặc một nhóm phần tử thỏa mãn các điều kiện cụ thể trong các cấu trúc dữ liệu (như mảng, danh sách liên kết, cây hoặc đồ thị).

Thuật toán tìm kiếm có thể được chia thành hai nhóm sau dựa trên cách thức triển khai:

Định vị các phần tử mục tiêu bằng cách duyệt qua cấu trúc dữ liệu, chẳng hạn như duyệt qua mảng, danh sách liên kết, cây và đồ thị.
Đạt được việc tra cứu phần tử hiệu quả bằng cách tận dụng cách tổ chức dữ liệu hoặc thông tin có trước về dữ liệu, chẳng hạn như tìm kiếm nhị phân, tìm kiếm dựa trên băm và tìm kiếm trên cây tìm kiếm nhị phân.

Vì những chủ đề này đã được giới thiệu trong các chương trước, các thuật toán tìm kiếm chắc hẳn đã quen thuộc với chúng ta. Trong phần này, chúng ta sẽ ôn tập lại chúng dưới một góc nhìn hệ thống hơn.

Tìm kiếm vét cạn¶

Tìm kiếm vét cạn định vị các phần tử mục tiêu bằng cách duyệt qua từng phần tử của cấu trúc dữ liệu.

"Tìm kiếm tuyến tính" áp dụng cho các cấu trúc dữ liệu tuyến tính như mảng và danh sách liên kết. Nó bắt đầu từ một đầu của cấu trúc dữ liệu và truy cập từng phần tử một cho đến khi tìm thấy phần tử mục tiêu hoặc đi đến đầu kia mà không tìm thấy phần tử mục tiêu.
"Tìm kiếm theo chiều rộng" (breadth-first search) và "tìm kiếm theo chiều sâu" (depth-first search) là hai chiến lược duyệt cho đồ thị và cây. Tìm kiếm theo chiều rộng bắt đầu từ nút ban đầu và tìm kiếm theo từng tầng, truy cập các nút từ gần đến xa. Tìm kiếm theo chiều sâu bắt đầu từ nút ban đầu, đi theo một đường dẫn đến tận cùng, sau đó quay lui và thử các đường dẫn khác cho đến khi toàn bộ cấu trúc dữ liệu được duyệt qua.

Ưu điểm của tìm kiếm vét cạn là tính đơn giản và khả năng áp dụng rộng rãi, không đòi hỏi tiền xử lý dữ liệu hay cấu trúc dữ liệu bổ sung.

Tuy nhiên, độ phức tạp thời gian của các thuật toán này là \(O(n)\), trong đó \(n\) là số lượng phần tử, do đó hiệu suất sẽ kém khi xử lý lượng dữ liệu lớn.

Tìm kiếm thích ứng¶

Tìm kiếm thích ứng tận dụng các thuộc tính của chính dữ liệu (chẳng hạn như thứ tự đã được sắp xếp) để tối ưu hóa quy trình tìm kiếm và định vị các phần tử mục tiêu một cách hiệu quả hơn.

"Tìm kiếm nhị phân" sử dụng tính chất được sắp xếp của dữ liệu để đạt được hiệu quả tìm kiếm cao, chỉ áp dụng cho mảng.
"Tìm kiếm dựa trên băm" sử dụng bảng băm để lưu trữ dữ liệu cần tìm kiếm dưới dạng các cặp khóa-giá trị, từ đó cho phép thực hiện các truy vấn hiệu quả.
"Tìm kiếm trên cây" hoạt động trên các cấu trúc cây cụ thể (chẳng hạn như cây tìm kiếm nhị phân), nhanh chóng loại trừ các nút bằng cách so sánh giá trị nút để định vị phần tử mục tiêu.

Ưu điểm của các thuật toán này là hiệu suất cao, với độ phức tạp thời gian đạt tới \(O(\log n)\) hoặc thậm chí là \(O(1)\).

Tuy nhiên, việc sử dụng các thuật toán này thường yêu cầu tiền xử lý dữ liệu. Ví dụ, tìm kiếm nhị phân yêu cầu sắp xếp trước mảng, trong khi tìm kiếm dựa trên băm và tìm kiếm trên cây đều yêu cầu cấu trúc dữ liệu bổ sung, và việc duy trì các cấu trúc dữ liệu này cũng đòi hỏi thêm chi phí thời gian và không gian bộ nhớ.

Tip

Các thuật toán tìm kiếm thích ứng thường được gọi là thuật toán tra cứu (lookup algorithms), chủ yếu được sử dụng để nhanh chóng truy xuất các phần tử mục tiêu trong các cấu trúc dữ liệu cụ thể.

Lựa chọn phương pháp tìm kiếm¶

Cho một tập dữ liệu có kích thước \(n\), chúng ta có thể sử dụng tìm kiếm tuyến tính, tìm kiếm nhị phân, tìm kiếm trên cây, tìm kiếm dựa trên băm và các phương pháp khác để tìm kiếm phần tử mục tiêu. Nguyên lý hoạt động của từng phương pháp được thể hiện trong hình dưới đây.

Hiệu suất và đặc điểm của các phương pháp này được tóm tắt trong bảng dưới đây.

Bảng So sánh hiệu suất của các thuật toán tìm kiếm

	Tìm kiếm tuyến tính	Tìm kiếm nhị phân	Tìm kiếm trên cây	Tìm kiếm dựa trên băm
Tìm kiếm phần tử	\(O(n)\)	\(O(\log n)\)	\(O(\log n)\)	\(O(1)\)
Chèn phần tử	\(O(1)\)	\(O(n)\)	\(O(\log n)\)	\(O(1)\)
Xóa phần tử	\(O(n)\)	\(O(n)\)	\(O(\log n)\)	\(O(1)\)
Không gian bổ sung	\(O(1)\)	\(O(1)\)	\(O(n)\)	\(O(n)\)
Tiền xử lý dữ liệu	/	Sắp xếp \(O(n \log n)\)	Xây dựng cây \(O(n \log n)\)	Xây dựng bảng băm \(O(n)\)
Thứ tự dữ liệu	Không có thứ tự	Có thứ tự	Có thứ tự	Không có thứ tự

Việc lựa chọn thuật toán tìm kiếm còn phụ thuộc vào lượng dữ liệu, yêu cầu hiệu suất tìm kiếm, tần suất truy vấn và cập nhật dữ liệu, v.v.

Tìm kiếm tuyến tính

Khả năng áp dụng rộng rãi, không đòi hỏi các thao tác tiền xử lý dữ liệu. Nếu chúng ta chỉ cần truy vấn dữ liệu một lần, thời gian tiền xử lý theo ba phương pháp kia thậm chí có thể lâu hơn cả bản thân quá trình tìm kiếm tuyến tính.
Phù hợp với lượng dữ liệu nhỏ, nơi độ phức tạp thời gian ít ảnh hưởng đến hiệu suất.
Phù hợp với các kịch bản có tần suất cập nhật dữ liệu cao, vì phương pháp này không đòi hỏi bất kỳ hoạt động duy trì dữ liệu bổ sung nào.

Tìm kiếm nhị phân

Phù hợp với các tập dữ liệu lớn, với hiệu suất ổn định và độ phức tạp thời gian trong trường hợp xấu nhất là \(O(\log n)\).
Lượng dữ liệu không thể quá lớn, vì việc lưu trữ mảng yêu cầu không gian bộ nhớ liên tục.
Không phù hợp với các kịch bản thường xuyên chèn và xóa dữ liệu, vì việc duy trì một mảng đã sắp xếp có chi phí rất cao.

Tìm kiếm dựa trên băm

Phù hợp với các kịch bản có yêu cầu cao về hiệu suất truy vấn, với độ phức tạp thời gian trung bình là \(O(1)\).
Không phù hợp với các kịch bản yêu cầu dữ liệu có thứ tự hoặc tìm kiếm phạm vi, vì bảng băm không thể duy trì dữ liệu theo thứ tự đã được sắp xếp.
Phụ thuộc nhiều vào hàm băm và chiến lược xử lý đụng độ băm, với rủi ro suy giảm hiệu suất đáng kể.
Không phù hợp với lượng dữ liệu quá lớn, vì bảng băm yêu cầu không gian bổ sung để giảm thiểu đụng độ, từ đó mang lại hiệu suất truy vấn tốt.

Tìm kiếm trên cây

Phù hợp với các tập dữ liệu cực lớn, vì các nút cây được lưu trữ không liên tục trong bộ nhớ.
Phù hợp với các kịch bản yêu cầu duy trì dữ liệu có thứ tự hoặc thực hiện tìm kiếm phạm vi.
Trong quá trình chèn và xóa nút liên tục, cây tìm kiếm nhị phân có thể bị lệch, làm suy giảm độ phức tạp thời gian xuống \(O(n)\).
Nếu sử dụng cây AVL hoặc cây đỏ-đen, mọi thao tác có thể chạy ổn định trong thời gian \(O(\log n)\), mặc dù việc duy trì sự cân bằng của cây sẽ phát sinh thêm chi phí.