ジャンプ探索

1. ジャンプ探索アルゴリズム
2. ジャンプ探索の例
3. ジャンプ探索アルゴリズムの実装
4. ジャンプ探索アルゴリズムの複雑さ

ジャンプ探索は、区間探索アルゴリズムです。これは、ソートされた配列のみで動作する比較的新しいアルゴリズムです。これは、線形探索のようにすべての要素を走査しないことで、線形探索よりも必要な比較回数を減らそうとしています。ジャンプ探索では、配列を m ブロックに分割します。あるブロック内の要素を探索し、要素が存在しない場合は次のブロックに移動します。アルゴリズムが要素を含むブロックを見つけると、線形探索アルゴリズムを用いて正確なインデックスを見つけます。このアルゴリズムは線形探索よりも高速ですが、バイナリ探索よりも遅くなります。

ジャンプ探索アルゴリズム

ここでは、n 個の要素を含むソートされていない配列 A[] があると仮定して、要素 X を見つけたいとします。

ジャンプ探索の例

配列 (1, 2, 3, 4, 5, 6, 7, 8, 9) があり、X - 7 を求めたいとします。

要素が 9 個あるので、n を 9 とします。

ジャンプ探索アルゴリズムの実装

#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) です。