蓄水池抽样算法

xiaoxiao2021-03-01  19

将N个球放入容积为K的袋子中,如何保证每个球仍然在袋子中的概率相同?

1.处理1-K号球时,直接放进袋子里;

2.处理第i号球时,以K/i的概率决定是否将第i号球放进袋子里。如果不决定将第i号球放进袋子里,直接扔掉第i号球;如果决定将第i号球放进袋子里,那么就从袋子里的K个球中随机选择一个扔掉,放入第i号球;

3.处理第i+1号球时,重复步骤1和2.

转载请注明原文地址: https://www.6miu.com/read-3350300.html

最新回复(0)