efficient running median

sturlamolden sturlamolden at yahoo.no
Tue Oct 13 20:57:33 CEST 2009

On 13 Okt, 18:33, Paul Rubin <http://phr...@NOSPAM.invalid> wrote:

> 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.

More information about the Python-list mailing list