蓄水池算法在抽奖中的应用
2021-03-18 21:26
阅读：330
标签：存储 算法 如何 时间复杂度 复杂 概率 复杂度 结果 个数 分析一下蓄水池算法在抽奖中的应用。 考虑参加抽奖的用户基数很大且未知，也可以说是这个基数可能会动态地增加，那么在这种情况下，固定选取k个人中奖，如何保证实时参加抽奖的n个用户中每个人中奖的概率为k/n呢？（为何不在最终结果n出来时再来随机抽取k个样本，保证概率为k/n呢？其实这种想法有些时候是不可行的，数据是动态增长的，可能缓存系统存储不了所有的样本信息，但却足够存储k个样本的信息，即空间复杂度可以从O(n)降到O(k)，k相对n来说是非常小的。所以储水池算法还是很有应用价值的） 1.先把前k个数放入蓄水池 2.对第i(i>k)个样本，以k/i概率决定换入蓄水池，换入时又随机选取池里的一个样本作为替换项 3.一直做下去，对于任意的样本空间n，对单个样本的选取概率为k/n 时间复杂度O(n) 空间复杂度O(1 ) https://kknews.cc/tech/om2jgrq.html 蓄水池算法在抽奖中的应用 标签：存储 算法 如何 时间复杂度 复杂 概率 复杂度 结果 个数 原文地址：https://www.cnblogs.com/garychen97/p/13795389.html蓄水池算法
应用场合
具体步骤
复杂度
参考文章
评论
亲，登录后才可以留言！