Content deleted Content added
m Dating maintenance tags: {{Empty-section}} |
→Space complexity: fill in |
||
Line 79:
== Space complexity ==
The required space complexity of selection is easily seen to be ''k'' + O(1) (or ''n'' − ''k'' if ''k'' > ''n''/2), and in-place algorithms can select with only O(1) additional storage. ''k'' storage is necessary as the following data illustrates: start with 1, 2, ..., ''k,'' then continue with ''k'' + 1, ''k'' + 1, ..., ''k'' + 1, and finally finish with ''j'' copies of 0, where ''j'' is from 0 to ''k'' − 1. In this case the ''k''th smallest element is one of 1, 2, ..., ''k,'' but this can only be determined at the end. One must store the initial ''k'' elements until near the end, since one cannot reduce the number of possibilities below the lowest ''k'' values until there are fewer than ''k'' elements left. Note that selecting the minimum (or maximum) by tracking the running minimum is a special case of this, with ''k'' = 1.
This space complexity is achieved by doing a progressive partial sort – tracking a sorted list of the lowest ''k'' elements so far, such as by the partial insertion sort above. Note however that selection by partial sorting, while space-efficient, has superlinear time complexity, and that time-efficient partition-based selection algorithms require O(''n'') space.
This space complexity bound helps explain the close connection between selecting the ''k''th element and selecting the (unordered) lowest ''k'' elements, as it shows that selecting the ''k''th element effectively requires selecting the lowest ''k'' elements as an intermediate step.
Space complexity is particularly an issue when ''k'' is a fixed fraction of ''n,'' particularly for computing the median, where ''k'' = ''n''/2, and in on-line algorithms. The space complexity can be reduced at the cost of only obtaining an approximate answer, or correct answer with certain probability; these are discussed below.
==Online selection algorithm==
| |||