Jump Search, Interpolation Search, QBS

Jump Search

Ordered Array에 대하여 search를 할 때 k의 배수번째 element만 check를 한다.

만약 check한 element가 찾고자 하는 원소의 value보다 작다면 계속 진행한다.

그렇지 않다면 그 전 원소들에 대하여 linear search를 진행한다.

 

Analysis of Jump Search

input size가 n이라고 하자.

만약 (m-1)k<n<=mk를 만족한다면, 총 cost는 최대 m+k-1이다.

최악의 경우는 Jump를 m번 하고 k-1개의 원소에 대하여 linear search를 하는 것이기 때문이다.

 

그렇다면 k를 어떠한 값으로 정해야 이 cost를 줄일 수 있을까?

 

미분을 해서 minimum일 때를 구해보면 k = n^(1/2)일 때 임을 알 수 있고, 그때의 cost는 2*n^(1/2)이다.

 

 

 

Interpolation Search

Sorted array에 대하여 item K를 찾는다고 가정해보자. 그러면 다음에 이동할 position은 다음과 같이 정해진다.

 

L은 sorted array이다.

이렇게 구한 p에 n을 곱하면 우리가 이동할 index가 정해진다.

이를 반복해서 포지션을 계속 정해서 찾아 나가는 search를 interpolation search라고 한다.

 

Quadratic Binary Search (QBS)

 

위에 interpolation search에서 구했던 position을 이용하여 원하는 값 K을 비교하면 세가지 경우가 나온다.

 

1. 원하는 값을 찾았을 때 : searh를 종료한다.

2. K<L[pn] : L[pn - i*n^(1/2)], i = 1, 2, 3....으로 jump search를 하면서 L를 훑는다.

3. K>L[pn] : 마찬가지로 jump search를 한다.

 

jump search를 하면 우리가 원하는 K 값 index 범위를 n^(1/2) 안으로 좁힐 수 있다.

그렇게 범위가 좁혀진다면 다시 jump search를 한다.

이를 반복하면 총 cost가 어떻게 될까?

 

QBS Cost

jump search를 할 때 probe 하는 횟수가 상수라고 가정하자(중요).

 

probe의 gap은 다음과 같아질 것이다. 

probe gap

그런데 n = 2^(logn)이므로 probe gap은 다음과 같이도 쓸 수 있다.

probe gap

이는 우리가 총 O(loglogn) 횟수가 필요하다는 것을 뜻하고, 각 횟수에서 jump search는 상수 시간을 소요하므로

cost는 O(loglogn)이다.

 

 

 

 

출처 : 서울대학교 컴퓨터공학부 강유 교수님 자료구조 수업