Content deleted Content added
→Space complexity: fill in |
m →Space complexity: wording |
||
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,'' depending on the number of 0s, 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.
| |||