보간검색

이 글은 검증을 위해 인용구가 추가로 필요하다. 신뢰할 수 있는 출처에 인용문을 추가하여 이 기사를 개선할 수 있도록 도와주십시오. 공급되지 않은 재료는 도전하여 제거할 수 있다. 출처 찾기: "인터폴레이션 검색" – 뉴스 · 신문 · 책 · 학자 · JSTOR (2017년 9월) (이 템플릿 메시지를 제거하는 방법과 시기 학습)

보간검색(Interpolation search)은 키(key value)에 할당된 숫자값(key value)에 의해 정렬된 배열에서 키를 검색하기 위한 알고리즘이다.1957년 W. W. 피터슨에 의해 처음 묘사되었다.^[1]보간 검색은 사람들이 전화번호부를 검색하여 이름(책의 입력을 명령하는 키 값)을 검색하는 방법과 유사하다. 각 단계에서 알고리즘은 검색 공간 범위 내의 키 값과 검색된 키, usu 값을 기준으로 검색된 항목이 있을 수 있는 위치를 계산한다.선형 보간법으로 동맹하다이 추정된 위치에서 실제로 발견되는 키 값을 추구하는 키 값과 비교한다.동일하지 않으면 비교에 따라 나머지 검색 공간은 추정 위치 이전 또는 이후의 부분으로 축소된다.이 방법은 키 값 간의 차이 크기에 대한 계산이 합리적일 경우에만 효과가 있을 것이다.

보간검색

24가 목표값인 보간 검색 알고리즘의 시각화.
클래스	검색 알고리즘
데이터 구조	배열
최악의 경우 공연	O(n)
베스트 케이스 공연	O(1)
평균 공연	O(log(log(n)))[2]
최악의 경우 공간 복잡성	O(1)

이에 비해 이진 검색은 항상 나머지 검색 공간의 중간을 선택하며, 예상 위치에서 찾은 키와 검색된 키의 비교에 따라 절반 또는 다른 키를 버린다. 즉, 키에 대한 숫자 값이 필요 없고 검색된 키에 대한 전체 순서가 필요하다.나머지 검색 공간은 추정 위치 이전 또는 이후의 부분으로 축소된다.선형 검색은 어떤 정렬도 무시한 채 처음부터 요소들을 하나씩 비교할 때만 평등을 사용한다.

평균적으로 보간 검색은 로그(log(n) 비교(요소가 균일하게 분포된 경우)에 대해 이루어진다. 여기서 n은 검색할 요소의 수입니다.최악의 경우(예를 들어 키의 숫자 값이 기하급수적으로 증가하는 경우) 최대 O(n) 비교를 할 수 있다.

보간-순차 검색에서는 보간법을 사용하여 검색 대상자 근처의 항목을 찾은 다음, 선형 검색을 사용하여 정확한 항목을 찾는다.

퍼포먼스

빅O 표기법을 사용하면 n 크기의 데이터 집합에 대한 보간 알고리즘의 성능은 O(n)이지만 보간법에 사용되는 선형 척도에 대한 데이터의 균일한 분포를 가정했을 때 그 성능은 O(log log n)^[3][4][5]로 보일 수 있다.단, 새로운 데이터 구조를 사용하여 o(log log n) 시간에 동적 보간 검색이 가능하다.^[6]

보간 검색의 실질적인 성능은 각 탐사에 필요한 더 복잡한 계산에 의해 줄어든 탐침 수가 더 큰지 여부에 달려 있다.각 프로브가 디스크 탐색에 포함되고 보간 산술보다 훨씬 느린 디스크의 큰 정렬된 파일에서 레코드를 찾는데 유용할 수 있다.

또한 B-tree와 같은 인덱스 구조는 디스크 액세스 수를 줄이고, 많은 유형의 데이터를 인덱싱할 수 있고 온라인에서 업데이트할 수 있기 때문에 디스크 내 데이터를 부분적으로 인덱싱하는 데 더 자주 사용된다.그러나 보간 검색은 특정 정렬되었지만 색인화되지 않은 디스크 데이터 집합을 검색하도록 강제될 때 유용할 수 있다.

다양한 데이터셋에 적응

데이터 집합에 대한 정렬 키가 균일하게 분포된 숫자일 경우 선형 보간법은 구현하기 쉬우며 검색 값에 매우 가까운 지수를 찾을 수 있다.

반면 이름별로 분류된 전화번호부의 경우 보간검색에 대한 직접적인 접근방식은 적용되지 않는다.그러나 동일한 높은 수준의 원칙이 여전히 적용될 수 있다: 이름의 상대적인 문자 빈도를 사용하여 전화번호부에서 이름의 위치를 추정할 수 있고 그것을 탐색 위치로 사용할 수 있다.

동일한 키 값의 실행이 존재하는 경우 일부 보간 검색 구현이 예상대로 작동하지 않을 수 있다.보간 검색의 가장 간단한 구현이 반드시 그러한 실행의 첫 번째(또는 마지막) 요소를 선택하는 것은 아니다.

책 기반 검색

전화번호부의 이름을 어떤 종류의 숫자로 변환하는 것은 분명히 균일한 분포를 가진 숫자를 제공하지 않을 것이며(이름을 분류하고 #1, 이름 #2 등이라고 부르는 엄청난 노력을 통해서는 제외), 나아가 어떤 이름들은 다른 이름들보다 훨씬 더 흔하다는 것은 잘 알려져 있다(Smith, Jones, ) 사전과 유사하게 wh몇몇 글자로 시작하는 단어들이 다른 단어들보다 더 많다.일부 출판사는 한 눈에 분할된 보간이 수행될 수 있도록 각 글자에 대한 마커를 보여주기 위해 한계 주석을 준비하거나 페이지 측면을 절단하는 노력을 기울인다.

샘플 구현

다음의 C++ 코드 예는 간단한 구현이다.각 단계에서 이항 검색과 마찬가지로 프로브 위치를 계산한 후, 검색 값을 포함하는 더 작은 간격을 정의하기 위해 상한 또는 하한을 이동시킨다.각 단계에서 간격 크기의 반을 보장하는 이진 검색과 달리 오도된 보간법은 O(n)의 효율을 감소시킬 수 있다.

/* T는 연산자 -, !=, ==, >=, <=, >, <=, <>를 실행해야 한다. 그러한 >=, <!=, ==, < T에 대한 총질서를 정의한다. 그런  (tm - tl) * k / (th번째 - tl)  tl <= tm <= t= tl!= tl!= tr!= tr. tl!= tr. tl!= tr. tl!= tr. tl!= tr. t. t. t. tl. t. t. t. t.  arr은 이 순서에 따라 분류되어야 한다.  \returns 이를 만족하는 i가 없는 경우 arr[i] == 키 또는 -1과 같은 인덱스 i. */ 템플릿 <타이프 이름 T> 인트로 보간_검색(T arr[], 인트로 사이즈를 맞추다, T 핵심을) {     인트로 낮은 = 0;     인트로 높은 = 사이즈를 맞추다 - 1;     인트로 중앙의;      하는 동안에 ((arr[높은] != arr[낮은]) && (핵심을 >= arr[낮은]) && (핵심을 <= arr[높은])) {         중앙의 = 낮은 + ((핵심을 - arr[낮은]) * (높은 - 낮은) / (arr[높은] - arr[낮은]));          만일 (arr[중앙의] < 핵심을)             낮은 = 중앙의 + 1;         다른 만일 (핵심을 < arr[중앙의])             높은 = 중앙의 - 1;         다른             돌아오다 중앙의;     }      만일 (핵심을 == arr[낮은])         돌아오다 낮은;     다른         돌아오다 -1; } 

루프 제어 관리의 이유로 색인 중간에서 목록을 검색한 경우 이 코드는 높음 또는 낮음을 중간이 아닌 인접 인덱스로 설정하고 다음 반복 중에 위치를 검색한다는 점에 유의하십시오.인접 입력의 값은 크게 다르지 않을 것이기 때문에 디스크와 같은 원거리 메모리에 대한 추가 참조 비용으로 이 한 단계 조정으로 보간 계산이 크게 개선되지 않는다.

반면 2진 검색 알고리즘 반복당 하나의 비교와로 쓰여질 수 있는 위의 코드의 각 반복 5~6비교(추가는 반복 사용하여<><>의 3개의 주를 구별하는 데 필요한;, 탭 2진 비교를 통해 3자 비교의 부재에 도착할 예정이다) 더한 지저분한 산술을 필요로 한다. o을 사용한다순전한 정수 산술따라서 20개 이하의 비교(배열 요소가 저장되는 느린 메모리에 대한 액세스 할당)를 통해 100만 개의 요소를 검색할 수 있으며, 이를 극복하기 위해 위에서 설명한 보간 검색은 3회 이하로 허용된다.

참고 항목

• 선형검색
• 이진 검색
• 지수 검색
• 3차 검색
• 해시 테이블
• 뉴턴의 방법
• 플래시 정렬, 검색 대신 정렬에 값 배포 사용

참조

외부 링크

• 보간검색
• 국립표준기술연구원
• 보간 검색 - 로그 LogN 검색