[EMAIL PROTECTED] wrote: > Quoting apfelmus <[EMAIL PROTECTED]>: >> 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. Regards, apfelmus _______________________________________________ Haskell-Cafe mailing list [EMAIL PROTECTED] http://www.haskell.org/mailman/listinfo/haskell-cafe
