Content deleted Content added
→Language support: space complexity section, details on C++ |
m reorder |
||
Line 80:
== Space complexity ==
{{empty-section}}
==Online selection algorithm==▼
In certain selection problems, selection must be online, that is, an element can only be selected from a sequential input at the instance of observation and each selection, respectively refusal, is irrevocable. The problem is to select, under these constraints, a ▼
specific element of the input sequence (as for example the largest or the smallest value) ▼
with largest probability. This problem can be tackled by the [[Odds algorithm]] designed by [[F. Thomas Bruss]] who coined the name Odds algorithm. It is also known as Bruss-algorithm or Bruss-strategy. This algorithm yields the optimal under an independence condition; it is also optimal itself as an algorithm with the number of computations being linear in the length of input.▼
== Language support ==
Line 91 ⟶ 96:
Because [[sorting algorithm#Language support|language support for sorting]] is more ubiquitous, the simplistic approach of sorting followed by indexing is preferred in many environments despite its disadvantage in speed. Indeed for [[Lazy evaluation|lazy languages]], this simplistic approach can even achieve the best complexity possible for the ''k'' smallest/greatest sorted (with maximum/minimum as a special case) if the sort is lazy enough.
▲==Online selection algorithm==
▲In certain selection problems, selection must be online, that is, an element can only be selected from a sequential input at the instance of observation and each selection, respectively refusal, is irrevocable. The problem is to select, under these constraints, a
▲specific element of the input sequence (as for example the largest or the smallest value)
▲with largest probability. This problem can be tackled by the [[Odds algorithm]] designed by [[F. Thomas Bruss]] who coined the name Odds algorithm. It is also known as Bruss-algorithm or Bruss-strategy. This algorithm yields the optimal under an independence condition; it is also optimal itself as an algorithm with the number of computations being linear in the length of input.
== References ==
| |||