Chào ace, bài này chúng ta sẽ tìm hiểu về một trong các thuật toán sắp xếp được sử dụng nhiều trong lập trình và thực tế nhất đó là Jump Search, sau đây cafedev sẽ giới thiệu và chia sẻ chi tiết(khái niệm, ứng dụng của nó, code ví dụ, điểm mạnh, điểm yếu…) về Jump Search thông qua các phần sau.
Nội dung chính
1. Giới thiệu
Giống như Tìm kiếm nhị phân, Tìm kiếm nhảy(Jump Search) là một thuật toán tìm kiếm các mảng được sắp xếp. Ý tưởng cơ bản là kiểm tra ít phần tử hơn (so với tìm kiếm tuyến tính) bằng cách nhảy lên trước bằng các bước cố định hoặc bỏ qua một số phần tử thay vì tìm kiếm tất cả các phần tử.
Ví dụ, giả sử chúng ta có một mảng arr [] kích thước n và khối (được nhảy) kích thước m. Sau đó, chúng tôi tìm kiếm tại các chỉ mục arr [0], arr [m], arr [2m]… ..arr [km], v.v. Khi chúng ta tìm được khoảng (arr [km] <x <arr [(k + 1) m]), chúng ta thực hiện phép toán tìm kiếm tuyến tính từ chỉ số km để tìm phần tử x.
Hãy xem xét mảng sau: (0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610). Độ dài của mảng là 16. Tìm kiếm theo bước nhảy sẽ tìm thấy giá trị là 55 với các bước sau giả sử rằng kích thước khối được nhảy là 4.
BƯỚC 1: Chuyển từ chỉ số 0 sang chỉ số 4;
BƯỚC 2: Chuyển từ chỉ số 4 sang chỉ số 8;
BƯỚC 3: Chuyển từ chỉ số 8 sang chỉ số 12;
BƯỚC 4: Vì phần tử ở chỉ số 12 lớn hơn 55 nên chúng ta sẽ lùi lại một bước để đến chỉ số 8.
BƯỚC 5: Thực hiện tìm kiếm tuyến tính từ chỉ số 8 để lấy phần tử 55.
Kích thước khối tối ưu được bỏ qua là bao nhiêu?
Trong trường hợp xấu nhất, chúng ta phải thực hiện n / m bước nhảy và nếu giá trị được kiểm tra cuối cùng lớn hơn phần tử cần tìm, chúng ta thực hiện so sánh m-1 nhiều hơn cho tìm kiếm tuyến tính. Do đó tổng số phép so sánh trong trường hợp xấu nhất sẽ là ((n / m) + m-1). Giá trị của hàm số ((n / m) + m-1) sẽ đạt cực tiểu khi m = √n. Do đó, kích thước bước tốt nhất là m = √n.
2. Code trên nhiều ngôn ngữ
C++
// C++ program to implement Jump Search
#include <bits/stdc++.h>
using namespace std;
int jumpSearch(int arr[], int x, int n)
{
// Finding block size to be jumped
int step = sqrt(n);
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[min(step, n)-1] < x)
{
prev = step;
step += sqrt(n);
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;
return -1;
}
// Driver program to test function
int main()
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 };
int x = 55;
int n = sizeof(arr) / sizeof(arr[0]);
// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x, n);
// Print the index where 'x' is located
cout << "\nNumber " << x << " is at index " << index;
return 0;
} Java
// Java program to implement Jump Search.
public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.length;
// Finding block size to be jumped
int step = (int)Math.floor(Math.sqrt(n));
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[Math.min(step, n)-1] < x)
{
prev = step;
step += (int)Math.floor(Math.sqrt(n));
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == Math.min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;
return -1;
}
// Driver program to test function
public static void main(String [ ] args)
{
int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610};
int x = 55;
// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x);
// Print the index where 'x' is located
System.out.println("\nNumber " + x +
" is at index " + index);
}
}
Python3
# Python3 code to implement Jump Search
import math
def jumpSearch( arr , x , n ):
# Finding block size to be jumped
step = math.sqrt(n)
# Finding the block where element is
# present (if it is present)
prev = 0
while arr[int(min(step, n)-1)] < x:
prev = step
step += math.sqrt(n)
if prev >= n:
return -1
# Doing a linear search for x in
# block beginning with prev.
while arr[int(prev)] < x:
prev += 1
# If we reached next block or end
# of array, element is not present.
if prev == min(step, n):
return -1
# If element is found
if arr[int(prev)] == x:
return prev
return -1
# Driver code to test function
arr = [ 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 ]
x = 55
n = len(arr)
# Find the index of 'x' using Jump Search
index = jumpSearch(arr, x, n)
# Print the index where 'x' is located
print("Number" , x, "is at index" ,"%.0f"%index)
C#
// C# program to implement Jump Search.
using System;
public class JumpSearch
{
public static int jumpSearch(int[] arr, int x)
{
int n = arr.Length;
// Finding block size to be jumped
int step = (int)Math.Floor(Math.Sqrt(n));
// Finding the block where element is
// present (if it is present)
int prev = 0;
while (arr[Math.Min(step, n)-1] < x)
{
prev = step;
step += (int)Math.Floor(Math.Sqrt(n));
if (prev >= n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while (arr[prev] < x)
{
prev++;
// If we reached next block or end of
// array, element is not present.
if (prev == Math.Min(step, n))
return -1;
}
// If element is found
if (arr[prev] == x)
return prev;
return -1;
}
// Driver program to test function
public static void Main()
{
int[] arr = { 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610};
int x = 55;
// Find the index of 'x' using Jump Search
int index = jumpSearch(arr, x);
// Print the index where 'x' is located
Console.Write("Number " + x +
" is at index " + index);
}
}
PHP
<?php
// PHP program to implement Jump Search
function jumpSearch($arr, $x, $n)
{
// Finding block size to be jumped
$step = sqrt($n);
// Finding the block where element is
// present (if it is present)
$prev = 0;
while ($arr[min($step, $n)-1] < $x)
{
$prev = $step;
$step += sqrt($n);
if ($prev >= $n)
return -1;
}
// Doing a linear search for x in block
// beginning with prev.
while ($arr[$prev] < $x)
{
$prev++;
// If we reached next block or end of
// array, element is not present.
if ($prev == min($step, $n))
return -1;
}
// If element is found
if ($arr[$prev] == $x)
return $prev;
return -1;
}
// Driver program to test function
$arr = array( 0, 1, 1, 2, 3, 5, 8, 13, 21,
34, 55, 89, 144, 233, 377, 610 );
$x = 55;
$n = sizeof($arr) / sizeof($arr[0]);
// Find the index of '$x' using Jump Search
$index = jumpSearch($arr, $x, $n);
// Print the index where '$x' is located
echo "Number ".$x." is at index " .$index;
return 0;
?>
Kết quả
Number 55 is at index 103. Độ phức tạp
Độ phức tạp thời gian: O (√n)
Không gian phụ trợ: O (1)
Điểm quan trọng:
- Chỉ hoạt động với các mảng được sắp xếp.
- Kích thước tối ưu của một khối được nhảy là (√ n). Điều này làm cho độ phức tạp về thời gian của Jump Search là O (√ n).
- Độ phức tạp về thời gian của Tìm kiếm nhảy là giữa Tìm kiếm tuyến tính ((O (n)) và Tìm kiếm nhị phân (O (Log n)).
- Tìm kiếm Nhị phân tốt hơn Tìm kiếm Nhảy, nhưng Tìm kiếm Nhảy có một ưu điểm là chúng ta chỉ duyệt lại một lần (Tìm kiếm Nhị phân có thể yêu cầu tối đa O (Nhật ký n) bước nhảy, hãy xem xét tình huống trong đó phần tử cần tìm là phần tử nhỏ nhất hoặc nhỏ hơn nhỏ nhất). Vì vậy, trong một hệ thống mà tìm kiếm nhị phân rất tốn kém, chúng tôi sử dụng Jump Search.
Nguồn và Tài liệu tiếng anh tham khảo:
Tài liệu từ cafedev:
- Full series tự học Cấu trúc dữ liệu và giải thuật từ cơ bản tới nâng cao tại đây nha.
- Ebook về Cấu trúc dữ liệu và giải thuật tại đây.
- Các series tự học lập trình khác
Nếu bạn thấy hay và hữu ích, bạn có thể tham gia các kênh sau của cafedev để nhận được nhiều hơn nữa:
Chào thân ái và quyết thắng!
