常数内存蓄水池抽样能否实现O(k)时间复杂度？流式抽样咨询

嘿，这个问题问得很精准，我来帮你拆解清楚：

一、常数内存蓄水池抽样能不能做到O(k)时间复杂度？ #

首先得明确前提：如果输入流的总大小n是已知的，那确实能做到**平均O(k)**的时间复杂度，但最坏情况还是O(n)。

常规的蓄水池抽样（比如经典的Algorithm R）得遍历整个输入流，时间复杂度是O(n)——因为它不需要提前知道n的大小。但如果n是已知的，就可以像你设计的算法那样，选够k个元素就直接终止遍历，这样平均下来处理的元素数量会远小于n，尤其是当n远大于k时，平均时间基本就接近O(k)了。不过运气极差的话（比如最后k个元素才凑够样本），还是得遍历完所有n个元素，所以最坏情况是O(n)。

要是n未知，那没办法提前终止，必须处理每个元素，时间复杂度只能是O(n)。

二、你的算法完全正确！ #

你给出的这个算法：

for each element in input stream
    if random()<k/n
        decrement k
        output element
        if k = 0
            halt
        end if
    end if
    decrement n
end for

完全符合你的需求：每个元素被选中的概率都是初始的k/n，而且全程只用常数内存，不需要额外存储选中的样本，直接输出就行。

我给你简单推导下正确性：假设初始总元素数是N，要选K个元素。对于第i个元素（此时还剩n=N-i+1个元素没处理，还需要选k个样本）：

• 这个元素被选中的概率是k/n；
• 不管它有没有被选中，后续元素的选中概率都会自动调整，最终所有元素被选中的总概率都是K/N，完全满足蓄水池抽样的公平性要求。

举个小例子验证：N=5，K=2。第一个元素被选中的概率是2/5；第二个元素被选中的概率是（1-2/5）*2/4 +（2/5）*1/4 = 8/20=2/5，和第一个元素概率一样，剩下的元素同理，所有元素被选中的概率都是2/5，没问题。

三、算法的时间复杂度细节 #

你的算法在选够k个元素后就会halt，所以：

• 最坏情况：运气太差，直到最后k个元素才选中，这时候得遍历全部n个元素，时间复杂度O(n)；
• 平均情况：当n远大于k时，平均处理的元素数大概是n*(1 - ((n-1)/n)^k)，近似等于k（因为(1-1/n)^k ≈ e^(-k/n)，n很大时这一项接近1 - k/n），所以平均时间复杂度是O(k)。

而且这个算法的内存开销真的是常数级的，只需要维护k和n两个变量，完全符合你“无需为选中样本额外分配内存”的需求。

内容的提问来源于stack exchange，提问作者markt1964