Thứ Ba, ngày 19 tháng 5 năm 2009

Tìm kiếm tuyến tính (Linear search)

Trong khoa học máy tính, tìm kiếm tuyến tính là một thuật toán thuộc nhóm các giải thuật tìm kiếm phục vụ cho việc cố gắng để tìm ra một giá trị nào đó trong một tập dữ liệu cho trước.

Nhiệm vụ này được thực hiện bằng cách kiểm tra mỗi phần tử trong danh sách (list hay array) một cách tuần tự cho tới khi một phần tử thích hợp được tìm thấy. Vì thuật toán này lần lượt xử lý trên toàn bộ miền dữ liệu nên số bước thực hiện sẽ từ từ tiến tới tối đa là N. Chính vì thế độ phức tạp của nó là O(N) với N là số phần tử trong tập dữ liệu mà việc tìm kiếm được tiến hành. Mã nguồn sau được trích từ thư viện VnSLib của IEEV sẽ cụ thể hóa thuật toán này trong thực hành với ngôn ngữ C.


Binh Nguyen - Bioz

Cảm nhận:

0 thảo luận:

Đăng nhận xét

chia sẻ cho chúng tôi ý tưởng hay khó khăn của bạn ...