Content deleted Content added
Undid revision 1173183558 by Patar knight (talk) Meaningless redundancy: "algorithm" is already in title and "computer science" follows from "algorithm". Short descriptions should be helpful in disambiguating searches; they should not be as vague and uninformative as possible. |
m →Exact numbers of comparisons: Knuth: First occurrence (and someone may not now) |
||
Line 60:
== Exact numbers of comparisons ==
[[File:Median of 5.svg|thumb|upright=0.9|Finding the median of five values using six comparisons. Each step shows the comparisons to be performed next as yellow line segments, and a [[Hasse diagram]] of the order relations found so far (with smaller=lower and larger=higher) as blue line segments. The red elements have already been found to be greater than three others and so cannot be the median. The larger of the two elements in the final comparison is the median.]]
[[Donald Knuth|Knuth]] supplies the following triangle of numbers summarizing pairs of <math>n</math> and <math>k</math> for which the exact number of comparisons needed by an optimal selection algorithm is known. The {{nowrap|<math>n</math>th}} row of the triangle (starting with <math>n=1</math> in the top row) gives the numbers of comparisons for inputs of <math>n</math> values, and the {{nowrap|<math>k</math>th}} number within each row gives the number of comparisons needed to select the {{nowrap|<math>k</math>th}} smallest value from an input of that size. The rows are symmetric because selecting the {{nowrap|<math>k</math>th}} smallest requires exactly the same number of comparisons, in the worst case, as selecting the {{nowrap|<math>k</math>th}} {{nowrap|largest.{{r|knuth}}}}
{{center|0}}
| |||