선택 알고리즘

선택 알고리즘(selection algorithm)은 컴퓨터 과학에서 리스트나 배열에서 가장 작은 k번째 수를 찾는 알고리즘이다. 이러한 수를 k번째 순서통계량으로 부른다. 여기에는 최소, 최대, 중앙의 요소들을 찾는 케이스들이 포함된다. O(n)-time (최악의 선형 시간) 선택 알고리즘들이 있으며, 구조화된 데이터에 대해서는 부선형(sublinear)의 성능을 낼 수 있다. 극단적인 상황에서는 정렬된 데이터 배열의 경우 O(1)도 가능하다. '선택'이라는 것은 최근접 이웃과 최단 경로 문제와 같은 더 복잡한 문제들의 하위 문제로 취급된다. 수많은 선택 알고리즘들은 정렬 알고리즘을 일반화함으로써 유래하며 이와는 반대로 일부 정렬 알고리즘들은 반복되는 선택적 응용으로서 유래할 수 있다.

가장 단순한 선택 알고리즘 케이스는 목록을 순회하면서 최소 또는 최대 요소를 찾는 것으로, 선택 정렬과 관련하여 관찰이 가능하다. 이와는 반대로 가장 난해한 선택 알고리즘의 케이스의 경우 중앙값을 찾는 것이다.

 같이 보기 
 수학적 최적화
 검색 알고리즘

 참고 자료 




 Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. . Section 5.3.3: Minimum-Comparison Selection, pp. 207–219.
 Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest, and Clifford Stein. Introduction to Algorithms, Second Edition. MIT Press and McGraw-Hill, 2001. . Chapter 9: Medians and Order Statistics, pp. 183–196. Section 14.1: Dynamic order statistics, pp. 302–308.


 외부 링크 
 "Lecture notes for January 25, 1996: Selection and order statistics", ICS 161: Design and Analysis of Algorithms, David Eppstein