인트로셀렉트

인트로셀렉트

학급	선택 알고리즘
data 구조	어레이
최악의 경우 성능	O(n log n)
베스트 케이스 성능	O(n)

컴퓨터 과학에서 인트로셀렉트(introselect, "내시 선택"의 줄임말)는 빠른 평균 성능과 최적의 최악의 성능을 가진 중앙값과 빠른 선택을 혼합한 선택 알고리즘이다.Introselect는 인트로소트 정렬 알고리즘과 관련되어 있습니다.이는 기본적인 퀵 선택 알고리즘과 퀵소트 알고리즘의 개량입니다.양쪽 모두 퀵알고리즘에서 시작되어 평균 퍼포먼스가 우수하고 오버헤드가 낮지만 퀵알고리즘이 그렇지 않으면 최적의 최악의 경우 알고리즘으로 돌아갑니다(오버헤드가 높아집니다).충분히 빠르게 진행되다두 알고리즘 모두 빠른 평균 성능과 최적의 최악의 경우 성능을 모두 갖춘 C++ 표준 라이브러리를 위한 범용 알고리즘을 제공하기 위해 David Musser가 (Musser 1997)에서 도입했습니다.따라서 성능 ^[1]요건을 강화할 수 있습니다.단, 인트로셀렉트를 사용하는 대부분의 C++ 표준 라이브러리 구현에서는 quickselect와 heapselect를 결합하여 최악의 경우 O(n log n)^[2]의 실행 시간을 갖는 다른 "인트로셀렉트" 알고리즘이 사용됩니다.

알고리즘

Introsort는 퀵소트와 힙소트의 하이브리드를 만들어 O(n log n) 최악의 동작을 유지하면서 퀵소트에 버금가는 실용적인 성능을 실현합니다.Introsort는 QuickSort에서 시작되므로 QuickSort가 작동하면 QuickSort와 비슷한 성능을 달성하고 QuickSort가 충분히 빠르게 진행되지 않으면 humpsort(최적의 최악의 성능을 가진)로 돌아갑니다.마찬가지로, 인트로셀렉트는 퀵셀렉트와 중위수를 결합하여 퀵셀렉트와 유사한 성능으로 최악의 경우 선형 선택을 달성합니다.

Introselect는 quickselect에서 낙관적으로 시작하여 충분히 진행되지 않고 너무 많이 반복될 경우에만 최악의 경우 선형 시간 선택 알고리즘(중간 알고리즘의 Blum-Floyd-Pratt-Rivest-Tarjan 중위수)으로 전환하여 작동합니다.스위칭 전략은 알고리즘의 주요 기술 내용입니다.재귀의 깊이를 일정하게 제한하는 것만으로는 충분치 않습니다.이렇게 하면 알고리즘이 충분히 큰 리스트에서 모두 전환되기 때문입니다.Musser는 몇 가지 간단한 접근법에 대해 설명합니다.

• 지금까지 처리된 하위 파티션의 크기 목록을 추적합니다.목록 크기를 절반으로 줄이지 않고k개의 재귀 콜이 실행된 경우, 일부 작은 양의 k에 대해서는 최악의 경우 선형 알고리즘으로 전환합니다.
• 지금까지 생성된 모든 파티션의 크기를 합산합니다.이 값이 목록 크기에 작은 양의 상수 k를 곱한 값을 초과할 경우 최악의 경우 선형 알고리즘으로 전환합니다.이 합계는 단일 스칼라 변수 내에서 쉽게 추적할 수 있습니다.

두 방법 모두 재귀 깊이를 k "log n" = O(log n)로 제한하고 총 실행 시간을 O(n)로 제한합니다.

이 논문은 인트로셀렉트에 대한 더 많은 연구가 예정되어 있다고 제안했지만, 저자는 더 이상의 연구를 발표하지 않고 2007년에 은퇴했다.

「 」를 참조해 주세요.

• Floyd-Rivest 알고리즘

레퍼런스