http://programmingpraxis.com/2009/12/11/selection/
On Thu, Sep 9, 2010 at 10:26 AM, David Van Horn <[email protected]>wrote: > 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 >
_________________________________________________ For list-related administrative tasks: http://lists.racket-lang.org/listinfo/users
