Selection Problem: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
Line 7: Line 7:
<span id='Order_Statistic'></span><span id='Order_Statistics'></span>The i<sup>th</sup> '''order statistic''' of a set of n numbers is the i<sup>th</sup> smallest number in the set.  
<span id='Order_Statistic'></span><span id='Order_Statistics'></span>The i<sup>th</sup> '''order statistic''' of a set of n numbers is the i<sup>th</sup> smallest number in the set.  


Finding the i<sup>th</sup> order statistic of a set is known as the ''selection problem''. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element. However, key comparison sorting [[Comparison_Sorting_Algorithms_Complexity|cannot be done more efficiently than Ω(n lgn)]], and more specialized and faster algorithms exist.
Finding the i<sup>th</sup> order statistic of a set is known as the '''selection problem'''. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element. However, key comparison sorting [[Comparison_Sorting_Algorithms_Complexity|cannot be done more efficiently than Ω(n lgn)]], and more specialized and faster algorithms exist.

Revision as of 01:42, 10 August 2018

Internal

Overview

The ith order statistic of a set of n numbers is the ith smallest number in the set.

Finding the ith order statistic of a set is known as the selection problem. Finding the median is a particular case of the selection problem. The selection problem can be resolved generically by sorting the entire set and then selecting the desired element. However, key comparison sorting cannot be done more efficiently than Ω(n lgn), and more specialized and faster algorithms exist.