점프 검색

Harshit Jindal 2023년10월12일
  1. 점프 검색 알고리즘
  2. 점프 검색 예
  3. 점프 검색 알고리즘 구현
  4. 점프 검색 알고리즘 복잡성
점프 검색

점프 검색은 간격 검색 알고리즘입니다. 정렬 된 배열에서만 작동하는 비교적 새로운 알고리즘입니다. 선형 검색과 같은 모든 단일 요소를 스캔하지 않음으로써 선형 검색보다 필요한 비교 수를 줄이려고합니다. 점프 검색에서 배열은m블록으로 나뉩니다. 한 블록에서 요소를 검색하고 요소가 없으면 다음 블록으로 이동합니다. 알고리즘이 요소를 포함하는 블록을 찾으면 선형 검색 알고리즘을 사용하여 정확한 인덱스를 찾습니다. 이 알고리즘은 선형 검색보다 빠르지 만 이진 검색보다 느립니다.

점프 검색 알고리즘

n요소를 포함하는 정렬되지 않은 배열A[]가 있다고 가정하고X요소를 찾으려고합니다.

  • i0으로 설정하고 블록 크기m√n으로 설정 한 첫 번째 요소부터 시작합니다.
  • A[min (m, n) -1]<Xi<n동안.
    • im으로 설정하고m√n만큼 증가시킵니다.
  • i> =n이면-1을 반환합니다.
  • A[i]<X동안 다음을 수행합니다.
    • i증가
    • imin(m, n)과 같으면-1을 반환합니다.
  • A[i]==X이면i를 반환합니다.
  • 그렇지 않으면-1을 반환합니다.

점프 검색 예

배열 :(1, 2, 3, 4, 5, 6, 7, 8, 9)가 있고 X-7을 찾고 싶다고 가정합니다.

9 개의 요소가 있으므로n9로 지정합니다.

  • i0으로,m√93으로 설정합니다.
  • A[2]X보다 작습니다. i3으로,m6으로 설정합니다.
  • A[5]X보다 작습니다. i6으로m9로 설정합니다.
  • A[8]X와 같습니다. 루프에서 벗어나십시오.
  • i6n보다 작기 때문입니다.
  • 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 avatar Harshit Jindal avatar

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

관련 문장 - Search Algorithm