Content deleted Content added
Lower bounds section and Knuth reference |
|||
Line 112:
When only the minimum (or maximum) is needed, a better approach is to use a [[priority queue]], which is able to find the minimum (or maximum) element in constant time, while all other operations, including insertion, are O(log ''n''). More generally, a [[self-balancing binary search tree]] can easily be augmented to make it possible to both insert an element and find the ''k''th largest element in O(log ''n'') time.
== Lower bounds ==
In his seminal ''[[The Art of Computer Programming]]'', Don Knuth discussed a number of lower bounds for the number of comparisons required to locate the ''k''th smallest entry of an unorganized list of ''n'' items (using only comparisons). There's a trivial lower bound of ''n'' − 1 for the minimum or maximum entry. To see this, consider a tournament where each game represents one comparison. Since every player except the winner of the tournament must lose a game before we know the winner, we have ''n'' − 1 comparisons.
The story becomes more complex for other indexes. To find the ''t''th smallest value requires at least this many comparisons:
:<math>n - t + \sum_{n+1-t < j \leq n} \lceil{\mathbf{lg} j}\rceil</math>
This bound is achievable for ''t''=2 but better, more complex bounds exist for larger ''t''.
== References ==
* M. Blum, R.W. Floyd, V. Pratt, R. Rivest and R. Tarjan, "Time bounds for selection," ''J. Cornput. System Sci''. 7 (1973) 448-461.
* [[Donald Knuth|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.
[[Category:Algorithms]]
| |||