Content deleted Content added
→Factories: ce |
→Factories: ce |
||
Line 31:
===Factories===
The deterministic selection algorithms with the smallest known numbers of comparisons, for values of <math>k</math> that are far from <math>1</math> {{nowrap|or <math>n</math>,}} are based on the concept of ''factories'', introduced in 1976 by [[Arnold Schönhage]], [[Mike Paterson]], and {{nowrap|[[Nick Pippenger]].{{r|spp}}}} These are methods that build [[partial order]]s of certain specified types, on small subsets of input values, by using comparisons to combine smaller partial orders. As a very simple example, one type of factory can take as input a sequence of single-element partial orders, compare pairs of elements from these orders, and produce as output a sequence of two-element totally ordered sets. The elements used as the inputs to this factory could either be input values that have not been compared with anything yet, or "waste" values produced by other factories. The goal of a factory-based algorithm is to combine together different factories, with the outputs of some factories going to the inputs of others, in order to eventually obtain a partial order in which one element (the {{nowrap|<math>k</math>th}} smallest) is larger than some <math>k-1</math> other elements and smaller than another <math>n-k</math> others. A careful design of these factories leads to an algorithm that, when applied to median-finding, uses at most <math>2.942n</math> comparisons. For other values {{nowrap|of <math>k</math>,}} the number of comparisons is {{nowrap|smaller.{{r|dz99}}}}
===Sublinear data structures===
| |||