Jump Search

Tram Ho

Tìm kiếm và sắp xếp luôn là một trong những điều chính cần biết và cải thiện. Giống như phân loại, tìm kiếm cũng nhận được sự quan tâm đặc biệt của các nhà khoa học máy tính. Hôm nay chúng ta sẽ tìm hiểu về một thuật toán tìm kiếm đặc biệt có tên là Jump sort.

Jump Search

Trong thế giới tính toán rộng lớn, hãy chuyển tìm kiếm bắt buộc lại với một thuật toán tìm kiếm cho các danh sách có thứ tự. Nó hoạt động bằng cách kiểm tra đầu tiên tất cả các mục ở rìa của mục khối trong đó m là kích thước của khối. Khi một mục được tìm thấy có kích thước lớn hơn khóa tìm kiếm, thì chúng tôi thực hiện kích thước tuyến tính để tìm vị trí chính xác của mục đó. Giá trị tối ưu của m là √n, trong đó n là độ dài của danh sách L. Bởi vì cả hai bước của thuật toán đều xem xét tối đa √n mục mà thuật toán chạy trong thời gian O (√n). Con số này biểu thị sự tốt hơn của nó so với tìm kiếm tuyến tính và kém hơn so với tìm kiếm nhị phân. Điểm đáng chú ý chính so với tìm kiếm nhị phân là tìm kiếm nhảy chỉ cần nhảy lùi một lần, trong khi tìm kiếm nhị phân có thể nhảy lùi lên log n lần. Đây có thể là một điểm mấu chốt nếu việc nhảy về phía sau mất nhiều thời gian hơn so với việc nhảy về phía trước.

Thuật toán

Dưới đây là thuật toán chung để triển khai tìm kiếm nhảy:

Đầu vào: mảng A đã sắp xếp có n phần tử

Đầu ra: Chỉ mục của mục được tìm kiếm hoặc -1

Các bước cho cơ chế này là:

  1. Đặt chỉ số bắt đầu, i thành 0 và kích thước bước, m thành √n.
  2. So sánh giữa A [i] với mặt hàng. Nếu A [i]! = Item và A [i] <item, thì hãy chuyển sang khối tiếp theo. Ngoài ra, hãy làm như sau:
  3. Lặp lại bước 2 cho đến khi m đi đến cuối mảng đã cho.
  4. Nếu A [i]> mục, sau đó di chuyển đến đầu khối hiện tại và thực hiện tìm kiếm tuyến tính.
  5. Tiếp tục quy trình này cho đến khi x đến cuối khối bước. và trả về -1 như không tìm thấy

Thực hiện

Dưới đây là quá trình triển khai tìm kiếm bước nhảy của ruby

Sự phức tạp

Chúng tôi xác định độ phức tạp về thời gian và không gian như sau:

Độ phức tạp về thời gian:

Vòng lặp while trong đoạn mã trên thực hiện n/m lần khi bộ đếm vòng lặp tăng m lần trong mỗi lần lặp. Vì giá trị tối ưu của m = √n, do đó, n / m = √n dẫn đến độ phức tạp về thời gian là O (√n).

Không gian phức tạp:

Độ phức tạp không gian của thuật toán này là O (1) vì nó không yêu cầu bất kỳ cấu trúc dữ liệu nào khác để thực hiện.

Tìm kiếm bước nhảy tối ưu hơn

Chắc chắn thời gian thực hiện của thuật toán này là O (√n), Có một phần cải tiến cho thuật toán này. nếu chúng ta cẩn thận xem, một khi chúng ta biết khoảng giá trị ở đâu, chúng ta có thể tối ưu hóa nó bằng cách áp dụng tìm kiếm nhảy một lần nữa trên khoảng đó. Ví dụ, giả sử độ dài danh sách là 1.000. Khoảng nhảy nên là: √1000 = 32. Vì chúng ta có thể quan sát kỹ hơn, chúng ta có thể sử dụng tìm kiếm nhảy với một bước mới √32≈6. Mỗi khi chúng tôi tìm thấy khoảng thời gian mong muốn, chúng tôi có thể áp dụng thuật toán tìm kiếm nhảy với nhiều bước nhỏ hơn. Cuối cùng bước sẽ là 1. Trong trường hợp đó, độ phức tạp của thuật toán không bị mắc kẹt vào O (√n). Bây giờ độ phức tạp của nó gần với giá trị logarit hơn. Hạn chế của phương pháp này là việc thực hiện phương pháp này được coi là khó hơn so với tìm kiếm nhị phân, trong đó độ phức tạp cũng là O (log (n)).

Mặc dù nó không phức tạp hơn tìm kiếm nhị phân về độ phức tạp và không thể hoạt động nếu không có danh sách được sắp xếp, nhưng tôi vẫn nghĩ rằng nó là một cách tốt để học hỏi và áp dụng trong không gian thích hợp. Vì vậy, bạn có thể nghiên cứu thêm nếu bạn nhận được một số hứng thú. Cảm ơn bạn

Tham khảo: https://www.tutorialspoint.com/Jump-Search

Chia sẻ bài viết ngay

Nguồn bài viết : Viblo