점프 검색

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)입니다.