找到有限空间的中位数的概率

Munro和Paterson在他们的论文《有限的存储空间中的选择和分类》中研究了这个问题。他们表明，您的算法要求k
=Ω（√n）才能以恒定概率成功，并且通过吸引有关一维随机游走的基本结果，这是渐近最优的。

如果我想证明绝对最优，那么我要做的第一件事就是考虑一个任意算法A，然后 将 其执行与算法A’ 耦合
，当A第一次偏离您的算法时，您的算法会代替它执行，并且然后尝试尽可能接近A。