On 9/9/10 10:04 AM, Prabhakar Ragde wrote:
I don't think vectors help very much in this case (median-finding). For
the given code, the O(n) access to the middle of the list is dominated
by the cost of the sorting, which is at least O(n log n) [*].
It is theoretically possible to compute the median in O(n) time, but the
method is complicated and not very practical. But sorting definitely
does too much work. If only the median (or the kth largest, a problem
called "selection") is needed, a method which is both practical and of
pedagogical interest stems from adapting Quicksort, which is a good
exercise after section 25.2 of HtDP. This has expected cost O(n) on
random data, and vectors offer no asymptotic advantage over lists. --PR
[*] Technically, "at least Omega(n log n)".
The original post got me interested in median algorithms and I started
to read up on the selection problem. Wikipedia (I know, I know) says
the same thing as you: medians can be computed in O(n) time and points
to selection as the way to do it. But I don't see how to use selection
to achieve a O(n)-time median algorithm -- selection (of the kth
largest/smallest element) is O(n), but that's were k is some fixed
constant. To compute the median, you let k=n/2 (right?), so it's no
longer constant. Can you point me to (or sketch) a O(n) method? Or
just correct me if my reasoning is going astray.
Thanks!
David
_________________________________________________
For list-related administrative tasks:
http://lists.racket-lang.org/listinfo/users
