Tổng quan
Jump Search (tìm kiếm nhảy) là thuật toán tìm kiếm cho mảng đã sắp xếp, tiến theo các khối có kích thước cố định thay vì từng phần tử một. Nó nhảy về phía trước một bước cố định cho đến khi vượt qua mục tiêu, rồi quét tuyến tính ngắn ngược lại trong khối cuối cùng.
Nó là điểm trung hòa giữa Linear Search và Binary Search: ít phép so sánh hơn quét toàn bộ, nhưng không có những bước nhảy tùy ý như tìm kiếm nhị phân — hữu ích khi việc nhảy lùi tốn kém hơn nhảy tiến.
Tìm kiếm nhảy bước hoạt động thế nào?
- Chọn kích thước bước cố định, thường là căn bậc hai của độ dài mảng (√n).
- Nhảy về phía trước step vị trí mỗi lần trong khi phần tử cuối của khối vẫn nhỏ hơn mục tiêu.
- Khi giá trị cuối khối bằng hoặc vượt mục tiêu, ngừng nhảy.
- Quét tuyến tính từ đầu khối đó tới cuối khối để định vị mục tiêu.
- Trả về chỉ số nếu tìm thấy, hoặc báo không tồn tại khi lần quét đã vượt qua giá trị của mục tiêu.
Khi nào nên dùng?
- Mảng đã sắp xếp khi việc nhảy lùi tốn kém, nên các bước nhảy tiến có giới hạn được ưu tiên hơn.
- Hệ thống mà truy cập tuần tự (tiến) nhanh hơn nhiều so với truy cập ngẫu nhiên.
- Một ví dụ giảng dạy về sự đánh đổi giữa quét O(n) và tìm kiếm nhị phân O(log n).
Phân tích độ phức tạp
Với kích thước bước √n, Jump Search thực hiện khoảng √n bước nhảy cộng một lần quét cuối tối đa √n phần tử, cho thời gian O(√n) ở trường hợp xấu nhất. Con số này nằm giữa O(n) của Linear Search và O(log n) của Binary Search. Nó cần mảng đã sắp xếp và dùng O(1) bộ nhớ phụ.
Câu hỏi thường gặp
Vì sao √n là kích thước bước tối ưu?
Tổng chi phí xấp xỉ (n/step) bước nhảy cộng step phép so sánh trong khối cuối. Tối thiểu hóa tổng này theo step cho ra step = √n, giúp cân bằng hai giai đoạn.
Jump Search có bao giờ tốt hơn Binary Search không?
Về mặt tiệm cận, O(log n) của Binary Search thắng, nhưng Jump Search chỉ luôn tiến rồi quét cục bộ, điều này có thể thân thiện hơn trên các thiết bị mà việc tua lùi hoặc truy cập ngẫu nhiên tốn kém.