algorithm - 具有最大内存效率的增量中值计算

Question

我有一个产生值(value)的过程并且我观察到了。当进程终止时，我想计算这些值的中位数。

如果我必须计算平均值，我可以只存储总和和生成值的数量，因此需要 O(1) 的内存。中位数怎么样？有没有一种方法可以节省存储所有值所带来的显而易见的 O(n) 时间？

编辑:对 2 种情况感兴趣:1) 流长度已知，2) 未知。

Answer 1

您将需要至少存储 ceil(n/2) 个点，因为前 n/2 个点中的任何一个都可能是中位数。只存储点并找到中位数可能是最简单的。如果保存 ceil(n/2) 个点是有值(value)的，那么将前 n/2 个点读入排序列表(二叉树可能是最好的)，然后随着新点的添加，丢弃低点或高点并保留跟踪两端抛出的点数。

编辑:

如果流长度未知，那么显然，正如 Stephen 在评论中观察到的那样，我们别无选择，只能记住所有内容。如果可能存在重复项，我们可以使用 Dolphins 存储值和计数的想法来节省一些内存。