[Haskell-cafe] k-minima in Haskell

Ian Lynagh igloo at earth.li
Fri Apr 13 10:09:14 EDT 2007


On Fri, Apr 13, 2007 at 07:32:20AM -0400, ajb at spamcop.net wrote:
> 
> Quoting Thomas Hartman <tphyahoo at gmail.com>:
> 
> > Does that mean you can have the k minima in O(n) time, where n is
> > length of list, which would seem to be an improvement?
> 
> It's worth considering what the theoretical minimum is.
> 
> You have n elements, and you need to locate a specific k-element
> permutation.  There are n! / (n-k)! such permutations.  You therefore
> need log(n! / (n-k)!) bits of information.
> 
> A binary comparison provides one bit of information.  So the number of
> comparisons that you need to get that much information is:
> 
>   O(log(n! / (n-k)!))
> = O(n log n - (n-k) log (n-k))
> = O(n log (n/(n-k)) + k log (n-k))
> 
> That looks right to me.  If k << n, then this simplifies to
> O(n + k log n), and if k is close to n, it simplifies to
> O(n log n + k).

Hmm, is something wrong with the following?:

Tuple each element with its position:                 O(n)
Find kth smallest element in linear time, as per [1]: O(n)
Filter list for elements <= kth smallest:             O(n)
Sort filtered list by position:                       O(k log k)
map snd to get the positions:                         O(k)

Total: O(n + k log k)

(the filter step will take care of elements with the same value as the
kth smallest, as the filter is also comparing element positions when the
values are the same).


Thanks
Ian

[1] http://en.wikipedia.org/wiki/Selection_algorithm



More information about the Haskell-Cafe mailing list