선택 알고리즘

위키백과, 우리 모두의 백과사전.

선택 알고리즘(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》. 

외부 링크[편집]

원본 주소 "https://ko.wikipedia.org/w/index.php?title=선택_알고리즘&oldid=33392541"