선택 알고리즘

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

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

같이 보기

[편집]

참고 자료

[편집]
  • Blum, M.; Floyd, R. W.; Pratt, V. R.; Rivest, R. L.; Tarjan, R. E. (August 1973). “Time bounds for selection” (PDF). 《Journal of Computer and System Sciences》 7 (4): 448–461. doi:10.1016/S0022-0000(73)80033-9. 
  • Floyd, R. W.; Rivest, R. L. (March 1975). “Expected time bounds for selection”. 《Communications of the ACM》 18 (3): 165–172. doi:10.1145/360680.360691. S2CID 3064709. 
  • Kiwiel, K. C. (2005). “On Floyd and Rivest's SELECT algorithm”. 《Theoretical Computer Science》 347 (1–2): 214–238. doi:10.1016/j.tcs.2005.06.032. 
  • Donald Knuth. The Art of Computer Programming, Volume 3: Sorting and Searching, Third Edition. Addison-Wesley, 1997. ISBN 0-201-89685-0. 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. ISBN 0-262-03293-7. Chapter 9: Medians and Order Statistics, pp. 183–196. Section 14.1: Dynamic order statistics, pp. 302–308.
  •  이 문서는 다음을 포함합니다: 퍼블릭 도메인 자료 출처: NIST 문서: Black, Paul E. “Select”. 《Dictionary of Algorithms and Data Structures》. 

외부 링크

[편집]