점프 검색
점프 검색은 간격 검색 알고리즘입니다. 정렬 된 배열에서만 작동하는 비교적 새로운 알고리즘입니다. 선형 검색과 같은 모든 단일 요소를 스캔하지 않음으로써 선형 검색보다 필요한 비교 수를 줄이려고합니다. 점프 검색에서 배열은m
블록으로 나뉩니다. 한 블록에서 요소를 검색하고 요소가 없으면 다음 블록으로 이동합니다. 알고리즘이 요소를 포함하는 블록을 찾으면 선형 검색 알고리즘을 사용하여 정확한 인덱스를 찾습니다. 이 알고리즘은 선형 검색보다 빠르지 만 이진 검색보다 느립니다.
점프 검색 알고리즘
n
요소를 포함하는 정렬되지 않은 배열A[]
가 있다고 가정하고X
요소를 찾으려고합니다.
-
i
를0
으로 설정하고 블록 크기m
을√n
으로 설정 한 첫 번째 요소부터 시작합니다. -
A[min (m, n) -1]
<X
및i
<n
동안.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