在线算法查找具有次线性 space 复杂度的中位数

Question

获得一项计划 algorithm/data-structure 的任务，该任务一个接一个地接收值，并可以在被询问时给出当前的中位数。 应该支持时间复杂度logn的值求值，输出时间复杂度恒定的中位数。

有没有办法用次线性 space 复杂度做到这一点？ 谢谢。

Answer 1

如果您已经看到 n 个数字，则可以通过添加更多数字来使每个数字成为当前中位数。所以不可能找到具有次线性 space 复杂度的解决方案。