3.2 水库抽样
本节介绍一个简单的空间亚线性算法，即水库抽样。问题定义如下。
抽样问题
输入：一组数据，但大小未知。
输出：这组数据的k个均匀抽样。
对于这个问题有三点要求：
1) 仅允许扫描数据一次。
2) 空间复杂度为O(k)。注意，空间复杂度和抽样大小有关，而与整个数据的数据量无关，这意味着不能把所有数据都放在内存当中进行抽样。
3) 扫描数据的前n个数据时(n>k)，要求保存当前已扫描数据的k个均匀抽样。这意味着在任何（n>k）时刻，在内存的k个数据里要放k个均匀的抽样。针对这个需求提出了水库抽样算法。算法3-1 水库抽样算法
1 申请一个长度为k的数组A保存抽样。
2 保存首先接收到的k个元素。
3 当接收到第i个新元素t时，以k/i的概率随机替换A中的元素。
随机替换可以生成［1,i］间的随机数j,若j≤k,就意味着j是存在的，则以t替换A［j］。
算法3-1的空间复杂度是
，这是因为在整个算法中，只需要一个长度为k的数组保存抽样。额外的空间（如计算概率）都是常数，与n和k没有关系，因此空间复杂度是O（k）。
算法3-1的抽样性质如定理3-1所示。
定理3-1 算法3-1得到的采样是均匀的，在任何时候接收到大于k的n个数时，选出的这k个数一定都是它的一个均匀采样。
证明 在接收第i+1个数时，第i个数还能保存在数组当中的概率是，因为在接收到第i+1个数时要以的概率随机替换，而第i个数被选中的概率是1k，它们相乘为就是第i个数被换出数组的概率，所以就是在接收第i+1个元素时第i个数在数组当中的概率。同理，在接收第i+2个数时，第i个数仍然保留在数组当中的概率是。依此类推，当接收第n个数时，第i个元素保存在数组当中的概率是。如果这些事件都发生了，那么在接收第n个数时，第i个数字才能保留在数组当中。因此它保留在抽样当中的概率是发生这些事件的概率的积，就是。■