Content deleted Content added
heapq nsmallest and nlargest have same complexity but the article had wrongly stated them to be different without citation to any source. |
|||
Line 88:
==Online selection algorithm==
[[online algorithm|Online]] selection may refer narrowly to computing the ''k''th smallest element of a stream, in which case partial sorting algorithms (with ''k'' + O(1)) space for the ''k'' smallest elements so far) can be used, but partition-based algorithms cannot be.
Alternatively, selection itself may be required to be [[online algorithm|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]], which 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.
| |||