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ư sắp xếp, tìm kiếm cũng nhận được sự chú ý đặc biệt từ 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 Jump sort.
Nhảy tìm kiếm
Trong thế giới rộng lớn của tính toán, nhảy tìm kiếm tương tự như một thuật toán tìm kiếm cho các danh sách theo thứ tự. Nó hoạt động bằng cách trước tiên kiểm tra tất cả các mục ở cạnh 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 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 nhìn vào, nhiều nhất, √n các 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à tồi tệ hơn tìm kiếm nhị phân. Ưu điểm chính của 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 nhị phân có thể nhảy ngược lên để đăng nhập n lần. Đây có thể là một điểm quan trọng nếu nhảy lùi mất nhiều thời gian hơn so với nhảy về phía trước.
Thuật toán
Dưới đây là thuật toán chung để thực hiện tìm kiếm nhảy:
Đầu vào: sắp xếp mảng A với n phần tử
Đầu ra: Chỉ mục của mục tìm kiếm hoặc -1
Các bước cho cơ chế này là:
Đặt chỉ mục bắt đầu, i thành 0 và kích thước bước, m thành n.
So sánh giữa A [i] với vật phẩm. Nếu A [i]! = Item và A [i] <item, sau đó nhảy sang khối tiếp theo. Ngoài ra, làm như sau:
123Reset index, i = step size,mIncrement step size, m by √nLặp lại bước 2 cho đến khi m đến cuối mảng đã cho.
Nếu mục A [i]>, 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.
123Set start of linear search, x = iCompare A[x] with item. If A[x]== item, then print x as the valid location else increment x by 1Tiếp tục thủ tục 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à triển khai ruby của tìm kiếm nhảy
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 | <span class="token keyword">def</span> jump_search array <span class="token punctuation">,</span> item n <span class="token operator">=</span> array <span class="token punctuation">.</span> size i <span class="token operator">=</span> <span class="token number">0</span> m <span class="token operator">=</span> <span class="token constant">Math</span> <span class="token punctuation">.</span> sqrt n <span class="token keyword">while</span> array <span class="token punctuation">[</span> m <span class="token punctuation">]</span> <span class="token operator"><=</span> item <span class="token operator">&&</span> m <span class="token operator"><</span> n <span class="token keyword">do</span> i <span class="token operator">=</span> m m <span class="token operator">+</span> <span class="token operator">=</span> <span class="token constant">Math</span> <span class="token punctuation">.</span> sqrt n <span class="token keyword">return</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">if</span> m <span class="token operator">></span> n <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">end</span> start <span class="token operator">=</span> i <span class="token keyword">while</span> start <span class="token operator"><</span> m <span class="token keyword">do</span> <span class="token keyword">return</span> x <span class="token keyword">if</span> a <span class="token punctuation">[</span> x <span class="token punctuation">]</span> <span class="token operator">==</span> item start <span class="token operator">+</span> <span class="token operator">=</span> <span class="token number">1</span> <span class="token keyword">end</span> <span class="token operator">-</span> <span class="token number">1</span> <span class="token keyword">end</span> |
Phức tạp
Chúng tôi xác định độ phức tạp của thời gian và không gian như sau:
Độ phức tạp 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 thêm m lần trong mỗi lần lặp. Do giá trị tối ưu của m = √n, do đó, n / m = n dẫn đến độ phức tạp thời gian của O (n).
Độ phức tạp không gian:
Độ 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 cấu trúc dữ liệu khác để thực hiện.
Tìm kiếm 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ũng 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 nhìn thấy, một khi chúng ta biết khoảng thời gian có giá trị, chúng ta có thể tối ưu hóa nó bằng cách áp dụng lại tìm kiếm nhảy trên khoảng đó. Ví dụ: giả sử chiều dài danh sách là 1.000. Khoảng thời gian nhảy phải là: √1000 = 32. Vì chúng ta có thể thấy gần, chúng ta có thể sử dụng tìm kiếm nhảy với bước mới √32≈6. Mỗi lần 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 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ị kẹt với 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ó khăn 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 mà không có danh sách được sắp xếp, nhưng tôi nghĩ rằng đó là một cách tốt để tìm hiểu và áp dụng trong không gian áp dụng. Vì vậy, bạn có thể nghiên cứu thêm nếu bạn nhận được một số quan tâm. Cảm ơn bạn
Tham khảo: https://www.tutorialspoint.com/Jump-Search