蓄水池抽样

蓄水池抽样是一个随机算法系列，用于从未知大小为n的群体中选择一个简单的随机样本，不需要替换，只需一次通过这些项目。算法不知道群体的大小，而且通常大到所有n个项目都能装进主内存。群体是随着时间的推移而显示给算法的，算法不能回看以前的项目。在任何时候，算法的当前状态必须允许提取一个简单的随机样本，而不需要对迄今为止看到的人口的一部分进行大小为k的替换。

假设我们看到一连串的项目，一次一个。我们想在内存中保留10个项目，并且我们想从序列中随机选择它们。如果我们知道项目的总数为n，并且可以任意访问这些项目，那么解决方案很简单：以相同的概率在1到n之间选择10个不同的索引i，并保留第i个元素。问题是，我们并不总是事先知道确切的n。简单。算法R一个简单而流行但缓慢的算法，算法R，是由AlanWaterman创造的。初始化一个数组{displaystylei=k}时，算法R返回所有输入。算法R返回所有输入，从而为数学归纳法的证明提供了基础。在这里，归纳假设是，一个特定的输入被包含在存储库中的概率正好在(i+1){displaystyle(i+1)}第1个输入被处理的概率为-第1个输入被处理的概率是ki{displaystyle{frac{k}{i}}}，我们必须证明，在处理第i+1}{displaystyle(i+1)}个输入之前，特定的输入被包含在存储库中的概率为ki而我们必须证明，一个特定的输入被包含在存储库中的概率是{displaystyle{frac{k}{i}}}times{left(1-{frac{1}{i+1}}}right)={frac{k}{i+1}}。.后面的结果来自于这样的假设：整数是均匀地随机生成的。

我们已经证明，一个新的输入进入储层的概率等于储层中现有输入被保留的概率。因此，我们根据数学归纳法的原理得出结论，算法R确实产生了一个随机的输入样本。虽然概念上简单易懂，但这个算法需要为输入的每一项产生一个随机数，包括被丢弃的项目。因此，该算法的渐进运行时间为O(n){displaystyleO(n)}。.如果输入群体很大，生成这种数量的随机性和线性运行时间会使算法变得不必要的缓慢。