thuật toán tìm kiếm tuần tự

Bách khoa toàn thư há Wikipedia

Tìm thám thính tuần tự
Phân loại giải thuật thám thính kiếm
Cấu trúc dữ liệu danh sách
Độ phức tạp thời gian O(n) Khi thành phần thám thính tìm tòi ở cuối list hoặc không tồn tại nhập danh sách
Thời gian ngoan chạy đảm bảo chất lượng nhất O(1) Khi thành phần cần thiết thám thính nằm ở đầu danh sách
Độ phức tạp ko gian O(n)

Trong Khoa học tập PC tìm thám thính tuần tự (tiếng Anh Sequential search) hoặc tìm thám thính tuyến tính (tiếng Anh linear search) là 1 trong cách thức thám thính tìm tòi một thành phần mang lại trước nhập một list bằng phương pháp duyệt theo thứ tự từng thành phần của list cơ cho tới khi nhìn thấy độ quý hiếm mong ước hoặc tiếp tục duyệt qua loa toàn cỗ list.

Bạn đang xem: thuật toán tìm kiếm tuần tự

Ứng dụng[sửa | sửa mã nguồn]

Tìm thám thính tuần tự là 1 trong giải thuật vô cùng đơn giản và giản dị Khi thực tế. Giải thuật này trầm trồ khá hiệu suất cao Khi cần thiết thám thính tìm tòi bên trên một list đầy đủ nhỏ hoặc một list ko chuẩn bị trật tự đơn giản và giản dị. Trong tình huống cần thiết thám thính tìm tòi rất nhiều lần, tài liệu thông thường được xử lý một chuyến trước lúc thám thính kiếm: hoàn toàn có thể được bố trí theo dõi trật tự, hoặc được thiết kế theo dõi một cấu tạo tài liệu đặc thù mang lại giải thuật hiệu suất cao rộng lớn,...

Mã giả[sửa | sửa mã nguồn]

Phiên bạn dạng lặp tự động nhiên[sửa | sửa mã nguồn]

Đây là phiên bạn dạng hoặc gặp gỡ nhất của giải thuật này, Search Engine Results Page được xem là địa điểm của thành phần cần thiết thám thính hoặc một độ quý hiếm Δ thể hiện tại việc không tìm kiếm thấy thành phần nhập list cơ.

 1. For each item in the list:
     1. if that item has the desired value,
         1. stop the tìm kiếm and return the item's location.
 2. Return 'Δ

Nếu list được tàng trữ bên dưới dạng mảng, địa điểm của thành phần cần thiết thám thính hoàn toàn có thể là chỉ số của chính nó nhập mảng, còn độ quý hiếm Δ hoàn toàn có thể là chỉ số ở trước thành phần đầu tien (0 hoặc -1 tùy nhập danh sách).

Xem thêm: Trang web VeBo TV - Xem live bóng đá hoàn toàn miễn phí

Nếu list là 1 trong list links, địa điểm của thành phần được trả về hoàn toàn có thể ở bên dưới dạng vị trí của no, còn độ quý hiếm Δ hoàn toàn có thể là độ quý hiếm null.

Phiên bạn dạng đệ quy[sửa | sửa mã nguồn]

Đây là phiên bạn dạng đệ quy Khi thực tế giải thuật thám thính tìm tòi tuần tự động.

Xem thêm: trường đại học nguyễn trãi

 1. if the list is empty, return Λ;
 2. else
    1. if the first item of the list has the desired value
       1. return its location;
    2. else 
       1. tìm kiếm the value in the remainder of the list, and return the result.

Sử dụng thành phần cụ canh[sửa | sửa mã nguồn]

Một cách thức được dùng nhằm nâng cấp hiệu suất cao của giải thuật là chèn thành phần mong muốn thám thính tìm tòi và cuối list như 1 thành phần cụ canh (sentinel) như được trình diễn bên dưới đây:

 1. Set A[n + 1] đồ sộ x. 
 2. Set i đồ sộ 1.
 3. Repeat this loop:
     1. If A[i] = x, 
        1. exit the loop.
     2. Set i đồ sộ i + 1.
 4. Return i.

Việc thêm thắt thành phần cụ canh canh ty giảm sút việc đối chiếu chỉ số thời điểm hiện tại i với số những thành phần n ở từng vòng lặp. Tuy nhiên, điều này chỉ hoàn toàn có thể được dùng Khi địa điểm ở đầu cuối của list tồn bên trên tuy nhiên không được dùng.

Tìm thám thính tuần tự động bên trên một list tiếp tục chuẩn bị xếp[sửa | sửa mã nguồn]

Trong những list và đã được bố trí tuy nhiên sẽ phải truy xuất tuần tự động như list links hoặc tệp tin cậy, việc thám thính tìm tòi tuần tự động tiếp tục hiệu suất cao rộng lớn trong vô số nhiều tình huống ko cần thiết duyệt toàn cỗ list vẫn Tóm lại được thành phần cơ ko xuất hiện. Tuy nhiên, với 1 mảng được bố trí, việc thám thính tìm tòi nhị phân trầm trồ hiệu suất cao nhập phần đông ngôi trường hợp

Tham khảo[sửa | sửa mã nguồn]