首页 > 代码库 > 蓄水池问题
蓄水池问题
for i in [n+1 N]
M=rand(1,i)
if(M<=n)
swap the ith and Mth data
证明方法:
1.初始情况,当尚未选择时,出现在pool中的n个元素的概率相同都是1,证明当第n+1葛元素以n/(n+1)的概率
被选中时,前n个元素在pool中的概率为n/(n+1)即可;
即任意元素被替换的概率为:n/(n+1)*1/n=1/(n+1)
所以前n个元素被替换的概率为n/(n+1)
1.假设当第i个元素以n/i的概率选中时,前i-1个元素被选中的概率同样n/i
2.证明当第i+1个元素以n/(i+1)的概率选中时,前i个元素被选中的概率同样为n/(i+1)
证明:第i+1个元素的情况为:前i个元素被选中的概率有两种情况:
a:如果第i+1次选择之前,这i个元素在pool中,有假设可知,前ige元素被选中的概率为n/i
b:第i+1此选择没有替换掉现在pool中元素:
先算任意元素被替换的概率:(n/(i+1))*(1/n)=1/(i+1)
因此没有被替换掉的概率为:1-1/(i+1)=i/(i+1)
ab相乘为:n/i*i/(i+1)=n/(i+1);
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。