승수 이진 검색
Multiplicative binary search | 이 글은 대부분의 독자들이 이해하기에는 너무 기술적인 것일 수도 있다.(2017년 9월)(이를 과 시기 |
 7이 목표값인 승수 이진 검색 알고리즘의 시각화. | |
| 클래스 | 검색 알고리즘 |
|---|---|
| 데이터 구조 | 배열 |
| 최악의 경우 공연 | O(log n) |
| 베스트 케이스 공연 | O(1) |
| 평균 공연 | O(log n) |
| 최악의 경우 공간 복잡성 | O(1) |
컴퓨터 과학에서 승수 이진 검색은 일반적인 이진 검색에서 사용하는 정렬 순서 대신 배열에서 특정 순열의 키를 사용하는 이진 검색의 변형이다.[1]다중적 이진 검색은 1980년에 토마스 스탠디쉬에 의해 처음 설명되었다.이 알고리즘은 효율적인 분할이나 교대조 운영 없이 소형 컴퓨터의 중간점 지수 계산을 단순화하기 위해 원래 제안되었다.현대 하드웨어에서는 다중 바이너리 검색의 캐시 친화적 특성으로 B-tree와 B+ 트리의 대안으로 블록 지향 스토리지의 아웃오브코어 검색에 적합하다.최적의 성능을 위해 B-트리 또는 B+-트리의 분기 계수는 저장되는 파일 시스템의 블록 크기와 일치해야 한다.승수 이진 검색에 사용되는 순열은 블록 크기에 관계없이 첫 번째(루트) 블록에 최적의 키 수를 배치한다.
다중적 이진 검색은 스위치 문을 구현하기 위해 컴파일러를 최적화하는 일부 컴파일러에 의해 사용된다.[2][3]
알고리즘.
다중 이진 검색은 순서가 지정된 정렬된 배열에서 작동한다.키는 해당 균형잡힌 바이너리 검색 트리의 레벨 순서 순서로 배열되어 저장된다.이것은 이진 검색의 첫 번째 피벗을 배열의 첫 번째 요소로 배치한다.두 번째 피벗은 다음 두 위치에 배치된다.
값이 A인0 n개 요소의 배열 A가 지정됨...An−1, 그리고 대상 값 T, 다음의 서브루틴은 A에서 T의 지수를 찾기 위해 승법적인 이진수 검색을 사용한다.
- i를 0으로 설정
- i n n이면 검색이 종료되지 않는다.
- Ai = T인 경우 검색이 완료되고 i를 반환하십시오.
- Ai < T일 경우, i를 2×i + 1로 설정하고 2단계로 이동하십시오.
- Ai > T일 경우, i를 2×i + 2로 설정하고 2단계로 이동하십시오.
참고 항목
인용구
- ^ Standish, Thomas A. (1980). "Chapter 4.2.2: Ordered Table Search". Data Structure Techniques. Addison-Wesley. pp. 136–141. ISBN 978-0201072563.
- ^ Sayle, Roger A. (17 June 2008). "A Superoptimizer Analysis of Multiway Branch Code Generation" (PDF). Proceedings of the GCC Developers' Summit: 103–116. Retrieved 4 March 2017.
- ^ Spuler, David A. (January 1994). Compiler Code Generation for Multiway Branch Statements as a Static Search Problem (Technical report). Department of Computer Science, James Cook University, Australia. 94/03.
