[Haskell-cafe] Time and space complexity of "take k . sort"
Paul Johnson
paul at cogito.org.uk
Thu Oct 22 10:31:55 EDT 2009
This question on StackOverflow asked about how to find the largest 100
items in a very long list:
http://stackoverflow.com/questions/1602998/fastest-way-to-obtain-the-largest-x-numbers-from-a-very-large-unsorted-list/1603198#1603198
I replied that you could do it with something like this (but here taking
the k smallest to strip out some irrelevant complications):
> takeLargest k = take k . sort
Because "sort" is lazily evaluated this only does enough sorting to find
the first k elements. I guess the complexity is something like
O(n*k*log(k)).
But of equal practical interest is the space complexity. The optimum
algorithm is to take the first k items, sort them, and then iterate
through the remaining items by adding each item to the sorted list and
then throwing out the highest one. That has space complexity O(k).
What does the function above do?
Paul.
More information about the Haskell-Cafe
mailing list