[Haskell-cafe] Re: k-minima in Haskell
apfelmus
apfelmus at quantentunnel.de
Sat Apr 14 06:33:32 EDT 2007
ajb at spamcop.net wrote:
> 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).
Ian Lynagh wrote:
> Hmm, is something wrong with the following?:
> [...]
> Total: O(n + k log k)
Mh, I'm not sure. At least, we have
log (n! / (n-k)!)
= log n! - log (n-k)!
= log 1 + log 2 + log 3 + ... + log (n-k) + ... + log n
- log 1 - log 2 - log 3 - ... - log (n-k)
= log (n-k +1) + ... + log (n-k +k)
which is greater than (k log (n-k)) and smaller than (k log n). For k=1,
this estimate yields a minimum time of (log n) to find the minimum of a
list. While not wrong, this clearly underestimates the necessary O(n).
I think that estimating (n log (n/(n-k)) to n for k << n is not correct
because the logarithm of 1 = n/n is 0 and not 1 :)
Ian Lynagh wrote:
> [1] http://en.wikipedia.org/wiki/Selection_algorithm
Thanks for the link, Ian. It clearly shows that a lazy
take k . qsort
takes only O(n + k log k) time. I posted an analysis as follow up to the
old thread on haskell-general
http://article.gmane.org/gmane.comp.lang.haskell.general/15110
Regards,
apfelmus
More information about the Haskell-Cafe
mailing list