蓄水池抽样算法概述(Reservoir Sampling Algorithm)[转载]

面京东被这个问题卡了QAQ,来补补这方面的课。

转自:链接

蓄水池抽样算法随机算法的一种,用来从 N 个样本中随机选择 K 个样本,其中 N 非常大(以至于 N 个样本不能同时放入内存)或者 N 是一个未知数。其时间复杂度为 O(N),包含下列步骤 (假设有一维数组 S, 长度未知,需要[……]

Read more