[Haskell-cafe] k-minima in Haskell
ajb at spamcop.net
ajb at spamcop.net
Fri Apr 13 07:32:20 EDT 2007
G'day all.
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).
Cheers,
Andrew Bromage
More information about the Haskell-Cafe
mailing list