Bách khoa toàn thư hé Wikipedia
| Tìm thăm dò tuần tự | |
| Phân loại | giải thuật thăm dò 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 dò tìm kiếm ở cuối list hoặc không tồn tại vô danh sách |
| Thời gian trá chạy chất lượng tốt nhất | O(1) khi thành phần cần thiết thăm dò 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 dò tuần tự (tiếng Anh Sequential search) hoặc tìm thăm dò tuyến tính (tiếng Anh linear search) là một trong những cách thức thăm dò tìm kiếm một thành phần cho tới trước vô một list bằng phương pháp duyệt theo lần lượt từng thành phần của list cơ cho tới khi nhìn thấy độ quý hiếm ước muốn hoặc tiếp tục duyệt qua quýt 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 dò tuần tự là một trong những giải thuật rất rất giản dị và đơn giản 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 dò tìm kiếm bên trên một list đầy đủ nhỏ hoặc một list ko chuẩn bị trật tự giản dị và đơn giản. Trong tình huống cần thiết thăm dò tìm kiếm rất nhiều lần, tài liệu thông thường được xử lý một thứ tự trước lúc thăm dò kiếm: rất có thể được bố trí bám theo trật tự, hoặc được kiến thiết bám theo một cấu tạo tài liệu đặc thù cho tớ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 dò hoặc một độ quý hiếm Δ thể hiện nay việc không tìm kiếm thấy thành phần vô 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 dò rất có thể là chỉ số của chính nó vô mảng, còn độ quý hiếm Δ rất có thể là chỉ số ở trước thành phần đầu tien (0 hoặc -1 tùy vô danh sách).
Xem thêm: xv là thế kỷ bao nhiêu
Nếu list là một trong những list links, địa điểm của thành phần được trả về rất có thể ở bên dưới dạng địa điểm của no, còn độ quý hiếm Δ rất 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 dò tìm kiếm tuần tự động.
Xem thêm: cách mở bài nghị luận xã hộ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ầm 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 dò tìm kiếm và cuối list như 1 thành phần cầm canh (sentinel) như được trình diễn bên dưới đây:
1. Set A[n + 1] to lớn x.
2. Set i to lớn 1.
3. Repeat this loop:
1. If A[i] = x,
1. exit the loop.
2. Set i to lớn i + 1.
4. Return i.
Việc tăng thành phần cầm canh gom 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ỉ rất 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 dò 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ẩn, việc thăm dò tìm kiếm 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 dò tìm kiếm nhị phân trầm trồ hiệu suất cao vô hầu như ngôi trường hợp
Bình luận