[Haskell-cafe] Re: k-minima in Haskell
apfelmus at quantentunnel.de
Fri Apr 13 04:28:03 EDT 2007
ajb at spamcop.net wrote:
> Quoting apfelmus <apfelmus at quantentunnel.de>:
>> You mean O(k * log n + n) of course.
> Erm, yes. You can do it in an imperative language by building a heap
> in O(n) time followed by removing k elements, in O(k log n) time.
Ah, sorry, there are indeed to variants not comparable to each other.
Threading a heap of k elements over the entire list needs O(n log k + k)
time and putting all of the list into a heap takes O(k log n + n) time.
For say k = O(sqrt(n)), the former is slower than the latter but it only
needs to keep O(k) list elements in memory.
I think that every k-minima algorithm of the form
take k . sort
has to keep all list elements in memory: the sort may not throw away
anything because it cannot know how many elements are requested.
More information about the Haskell-Cafe