蓄水池抽样算法概述(Reservoir Sampling Algorithm)[转载]Mar 9, 2017·3 mins其他 蓄水池抽样面京东被这个问题卡了QAQ，来补补这方面的课。 转自：链接 蓄水池抽样算法随机算法的一种，用来从 N 个样本中随机选择 K 个样本，其中 N 非常大（以至于 N 个样本不能同时放入内存）或者 N 是一个未知数。其时间复杂度为 O(N),包含下列步骤 (假设有一维数组 S, 长度未知，需要从中随机选择 k 个元素, 数组下标从 1 开始), 伪代码如下: