ジャンプ探索
![ジャンプ探索](/img/Algorithm/feature-image---jump-search.webp)
ジャンプ探索は、区間探索アルゴリズムです。これは、ソートされた配列のみで動作する比較的新しいアルゴリズムです。これは、線形探索のようにすべての要素を走査しないことで、線形探索よりも必要な比較回数を減らそうとしています。ジャンプ探索では、配列を m
ブロックに分割します。あるブロック内の要素を探索し、要素が存在しない場合は次のブロックに移動します。アルゴリズムが要素を含むブロックを見つけると、線形探索アルゴリズムを用いて正確なインデックスを見つけます。このアルゴリズムは線形探索よりも高速ですが、バイナリ探索よりも遅くなります。
ジャンプ探索アルゴリズム
ここでは、n
個の要素を含むソートされていない配列 A[]
があると仮定して、要素 X
を見つけたいとします。
-
最初の要素から
i
を0
とし、ブロックサイズm
を√n
とする。 -
A[min(m,n)-1]
<X
とi
<n
の間に、A[min(m,n)-1]
を設定する。i
をm
とし、m
を√n
でインクリメントします。
-
i
>=n
の場合は-1
を返す。 -
A[i]
<X
の間は以下のようにする。i
をインクリメントします。i
がmin(m,n)
に等しい場合は-1
を返します。
-
A[i]
==X
の場合はi
を返します。 -
そうでなければ
-1
を返す。
ジャンプ探索の例
配列 (1, 2, 3, 4, 5, 6, 7, 8, 9)
があり、X - 7
を求めたいとします。
要素が 9 個あるので、n
を 9
とします。
-
i
を0
とし、m
を√9
とすると、3
となる。 -
A[2]
はX
よりも小さい。i
を3
とし、m
を6
とする。 -
A[5]
はX
よりも小さい。i
を6
とし、m
を9
とします。 -
A[8]
はX
と等しい。ループから抜け出す。 -
i
を6
とするとn
より小さい。 -
A[6]
==7
. ループから抜け出す。 -
A[6]
==7
なので、6
を返す。
ジャンプ探索アルゴリズムの実装
#include <bits/stdc++.h>
using namespace std;
int jumpSearch(int arr[], int x, int n) {
int m = sqrt(n);
int i = 0;
while (arr[min(m, n) - 1] < x) {
i = m;
m += sqrt(n);
if (i >= n) return -1;
}
while (arr[i] < x) {
i++;
if (i == min(m, n)) return -1;
}
if (arr[i] == x) return i;
return -1;
}
int main() {
int n = 10;
int arr[] = {0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
int x = 7;
int result = jumpSearch(arr, x, n);
if (result == -1)
cout << "Element not found";
else
cout << "Element found at index " << result;
}
ジャンプ探索アルゴリズムの複雑さ
時間計算量
- 平均ケース
ジャンプソートアルゴリズムは n/m
回実行され、n
は要素数、m
はブロックサイズです。線形探索では、m-1
の比較が必要であり、合計の時間式は n/m + m-1
となります。時間式を最小化する m
の最適値は √n
であり、時間複雑度は n/√n + √n
、すなわち √n
となります。ジャンプ探索アルゴリズムの時間複雑度は O(√n)
です。
- 最良の場合
最良の時間的複雑さは O(1)
です。これは探索対象の要素が配列内に最初に存在する場合に発生します。
- 最悪の場合
最悪の場合は n/m
ジャンプを行い、最後にチェックした値が探索する要素よりも大きい場合で、線形探索のために m-1
比較が行われる。最悪の場合の時間的複雑さは O(√n)
です。
空間計算量
このアルゴリズムは一時変数以外のデータ構造を必要としないので、空間複雑度は O(1)
です。
Harshit Jindal has done his Bachelors in Computer Science Engineering(2021) from DTU. He has always been a problem solver and now turned that into his profession. Currently working at M365 Cloud Security team(Torus) on Cloud Security Services and Datacenter Buildout Automation.
LinkedIn