蓄水池算法（Reservoir Sampling Algorithm）是一種隨機算法，用於從未知數量的數據流中隨機選擇k個元素，其中k為預設的正整數。該算法的主要思想是在不知道數據流長度的情況下，通過隨機選擇k個元素並將其標記為「蓄水池」，然後從第k+1個元素開始，每個元素被選中的機率與之前未被選中的元素數量成比例。在完成蓄水池算法後，可以得到一個大小為k的隨機樣本，其中每個元素被選中的機率相等。
蓄水池算法的詳細步驟如下：
初始化：將前k個元素標記為「蓄水池」，並將其餘元素標記為未選中。
從第k+1個元素開始遍歷數據流：對於每個新元素，以k/n的機率將其標記為「蓄水池」（其中n是數據流中元素的總數）。如果元素被標記為「蓄水池」，則將其加入蓄水池中，並從數據流中移除。如果元素未被標記為「蓄水池」，則將其保留在數據流中。
重複步驟2直到數據流中的所有元素都被處理。
蓄水池算法的時間複雜度為O(mn)，其中m是數據流中的元素數量，n是每個元素的複雜度，因為需要對每個元素進行標記和移除操作。