알고리즘 - 검색 건너뛰기

예를 들어 크기가 n인 배열 arr[]과 크기가 m인 블록(점프 대상)이 있다고 가정합니다. 그런 다음 arr[0], arr[m], arr[2m]... ..arr[km] 등의 인덱스를 검색합니다. 간격(arr [km]

)을 찾으면

다음 배열을 고려합니다: (0,1,1,2,3,5,8,13,21,34,55,89,144,233,377,610). 배열의 길이는 16입니다. 건너뛸 블록 크기가 4라고 가정하면 건너뛰기 검색은 다음 단계에서 55를 찾습니다.

1단계: 인덱스 0에서 인덱스 4로 점프합니다.
2단계: 인덱스 4에서 인덱스 8로 점프합니다.
3단계: 인덱스 8에서 인덱스 16으로 점프합니다.
4단계: 인덱스 16의 요소가 55보다 크므로 인덱스 9로 한 단계 뒤로 이동합니다.
5단계: 인덱스 9에서 선형 검색을 수행하여 요소 55를 가져옵니다.
건너뛸 최적의 청크 크기는 얼마인가요?
최악의 경우, 마지막으로 확인한 값이 검색 중인 요소보다 큰 경우 n/m 점프를 수행하고 선형 검색으로 m-1 비교를 수행해야 합니다. 따라서 최악의 경우 총 비교 횟수는 ((n/m) + m-1)이 됩니다. m =√n일 때 함수의 값 ((n/m) + m-1)은 최소값이 됩니다. 따라서 가장 좋은 단계 크기는 m = √n입니다.

으아악

출력:

번호 55는 인덱스 10에 있습니다

시간 복잡도: O(√n)
보조공간 : O(1)

주의:

이 검색은 정렬된 배열에서만 작동합니다.
건너뛸 청크의 최적 크기는 O(√n)입니다. 이는 점프 탐색을 O(√n) 시간 복잡도로 만듭니다.
스킵 검색의 시간 복잡도는 선형 검색((O(n)))과 이진 검색(O(Log n)
) 사이입니다. 이진 검색은 점프 검색보다 낫지만 점프 검색은 한 번만 탐색한다는 장점이 있습니다(이진 검색은 검색되는 요소가 가장 작은 요소이거나 가장 작은 요소보다 작다는 점을 고려하여 최대 0(Log n) 점프가 필요할 수 있습니다). 따라서 점프 백 비용이 많이 드는 시스템에서는 점프 검색을 사용합니다.

위 내용은 알고리즘 - 검색 건너뛰기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!