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à:
- Đặt chỉ số 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 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:123Reset index, i = step size,mIncrement step size, m by √n
- Lặp lại bước 2 cho đến khi m đi đến cuối mảng đã cho.
- 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.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 1
- 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
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> <span class="token method-definition"><span class="token function">jump_search</span></span> 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> |
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