shenyongsi的博客

原创 蓄水池抽样算法

蓄水池抽样算法算法简介基本原理算法正确性证明算法的实现运行结果如下算法的局限性 算法简介 蓄水池抽样算法是随机算法的一种，用来从 N 个样本中随机选择 m 个样本，其中 N 非常大（以至于 N 个样本不能同时放入内存），且 N 是一个未知数。请问如何在只遍历一遍数据（O(N)）的情况下，能够随机选取出m个不重复的数据。 综上，可以提炼出以下三点： 数据流长度N很大且不可知，所以不能一次性存入内存； 时间复杂度为O(N)； 随机选取m个数，每个数被选中的概率为m/N； 第1点限制了不能直接取N内的m个随机