efficient running median

Paul Rubin http
Tue Oct 13 21:59:47 CEST 2009

sturlamolden <sturlamolden at yahoo.no> writes:
> > The obvious way to compute a running median involves a tree structure
> > so you can quickly insert and delete elements, and find the median.
> > That would be asymtotically O(n log n) but messy to implement.
> QuickSelect will find the median in O(log n) time.

That makes no sense, you can't even examine the input in O(log n) time.

Anyway, the problem isn't to find the median of n elements.  It's to
find n different medians of n different sets.  You might be able to
get close to linear time though, depending on how the data acts.

More information about the Python-list mailing list