Sort one sequence by O(n) in time and O(1) in space
Tim Daneliuk
tundra at tundraware.com
Tue Feb 11 06:37:26 CET 2014
On 02/10/2014 04:20 AM, Sturla Molden wrote:
> In general, we cannot sort a sequence in O(n) time. O(n log n) is the lower
> bound on the complexity.
Only true for sorting that involve comparison. However, sorts that use
the values of the inputs as positional keys have a lower bound
complexity (omega) of O(n) and a worst case complexity of O(n)
and are thus asymptotically optimal.
For example, given a range of integers guaranteed to be within
the range of j to k (lower to higher), one can created a bit field
to represent all possible values of j to k. Then, as values are
read in, the corresponding but is set true. You have to process
the list of n elements once to read it in, and then a second
time to read them out in order. This is a 2n operation which is O(n).
For very large ranges of j to k, this is impractical and we resort
to things like hashing functions which can perform better than
n log n sorting algorithms. But there are lots of real world
applications where inputs-as-keys works just fine, such as short
dispatch tables in operating systems where the value to be
sorted represents a process priority, for example.
--
----------------------------------------------------------------------------
Tim Daneliuk tundra at tundraware.com
PGP Key: http://www.tundraware.com/PGP/
More information about the Python-list
mailing list