점프 검색

컴퓨터 과학에서 점프 검색 또는 블록 검색은 순서 목록의 검색 알고리즘을 말합니다.검색 키보다 큰 항목이 발견될 때까지 먼저 모든_km 항목 L(${\displaystyle k\mathbb{}}$n$$N \ $displaystyle k\in$ \$mathbb${N$$$}$ ), m은 블록 크기)을 확인합니다.리스트내의 검색 키의 정확한 위치를 찾기 위해서, 서브 리스트_{[(k-1)m, km]} L에 대해서 선형 검색을 실시한다.

m의 최적값은 µn입니다.여기서 n은 리스트 L의 길이입니다.알고리즘의 양쪽 스텝은 최대 n개의 아이템을 조사하기 때문에 알고리즘은 O(n)시간 내에 실행됩니다.이것은 선형 검색보다는 낫지만 이진 검색보다는 나쁩니다.후자에 비해 장점은 점프 검색은 한 번만 뒤로 점프하면 되고 바이너리 검색은 뒤로 점프하여 n번 기록할 수 있다는 것입니다.만약 뒤로 점프하는 것이 앞으로 점프하는 것보다 훨씬 더 많은 시간이 걸린다면, 이것은 중요하다.

알고리즘은 최종적으로 선형 검색을 수행하기 전에 하위 목록에서 여러 레벨의 점프 검색을 수행하여 수정할 수 있습니다.k 레벨 점프 검색의 경우, l 레벨 ^th(1부터 카운트)에 대한 최적의 블록 크기_l m은 n이다^(k-l)/k.수정된 알고리즘은 O(kn^1/(k+1)) 시간 내에 k개의 후방 점프와 실행을 수행합니다.

실행

Jump Search 알고리즘 입력:순서 목록 L, 길이 n 및 검색 키 출력:L에서의 s의 위치 또는 s가 L에 없는 경우 아무것도 반환하지 않는다.a ← 0 b ← 0 b ← 0 b + 0 n인 경우min(b,n)-1, L > s는 a ← min(b, n)인 경우, 아무것도 반환하지 않는 경우a, La < s는 a ← a + 1인 경우, L = s는 아무것도 반환하지 않는다.

「 」를 참조해 주세요.

• 스킵 리스트
• 보간 검색
• 선형 검색 - O(n) 시간 내에 실행되며 앞만 봅니다.
• 바이너리 검색 - O(log n) 시간 내에 실행되며 앞뒤로 모두 이동합니다.

레퍼런스

• 이 문서에는 NIST 문서의 퍼블릭 도메인 자료가 포함되어 있습니다.Black, Paul E. "jump search". Dictionary of Algorithms and Data Structures.
• Ben Shneiderman, Jump Searching: 빠른 시퀀셜 서치 테크닉, CACM, 21(10):831-834, 1978년 10월.