为什么中位数比例这么好？

Question

我最近在一次求职面试中遇到的一个问题是：

Write a data structure that supports two operations.
1. Adding a number to the structure.
2. Calculating the median.
The operations to add a number and calculate the median must have a minimum time complexity.

我的实现非常简单，基本上保持元素的排序，这样添加一个元素的代价是O（log（n））而不是O（1），但是中值是O（1）而不是O（n*log（n））

我还添加了一个简单的实现，但包含numpy数组中的元素：

^{pr2}$

下面是10^4个元素的表现：

对于10^5个元素，朴素的numpy实现实际上更快：

我的问题是： 怎么会？即使numpy以一个常数因子更快，如果它们不保留数组的排序版本，它们的中值函数如何伸缩得如此好？在

Answer 1

我们可以检查median（source）的Numpy源代码：

def median(a, axis=None, out=None, overwrite_input=False, keepdims=False):
    ...

    if overwrite_input:
        if axis is None:
            part = a.ravel()
            part.partition(kth)
        else:
            a.partition(kth, axis=axis)
            part = a
    else:
        part = partition(a, kth, axis=axis)

...

关键函数是partition，它来自docs，使用introselect。正如@zython评论的那样，这是Quickselect的变体，它提供了关键的性能提升。在