《Programming Pearls》第一版第 120 页介绍了从 N 个整数总体中选择 M 个等概率随机元素的算法。
InitToEmpty
Size := 0
While Size < M do
T := RandInt(1,N)
if not Member(T)
Insert(T)
Size := Size + 1
规定Member测试的预期数量小于2M，只要M
我想知道如何证明这一点，但我的算法分析背景让我失望。
我知道 M 越接近 N，程序花费的时间就越长，因为结果集将包含更多元素，并且 RandInt 选择现有元素的可能性将成比例增加。
你能帮我找出这个证明吗？
我不是数学奇才，但我会粗略地尝试一下。但这并不能保证是正确的。
对于 M 的每个附加成员，您选择一个数字，查看它是否存在，如果存在则添加它。否则，你再试一次。尝试某件事直到成功称为几何概率分布。
http://en.wikipedia.org/wiki/Geometric_distribution http://en.wikipedia.org/wiki/Geometric_distribution
所以您正在运行 M 次几何试验。每次试验都有预期值 1/p，因此将采取预期 1/p 尝试获取 M 中尚未存在的数字。p 是 N 减去我们已经从 M 添加的数字数量除以 N（即有多少未挑选的项目） / 总项目）。因此，对于第四个数字， p = (N -3) / N ，这是挑选未使用的数字的概率，因此第三个数字的预期挑选数量为 N / N-3 。
运行时间的预期值是所有这些值的总和。所以像
E(运行时间) = N/N + N/(N -1) + N/(N -2 ) ... + N/ (N-M)
现在，如果 M
问我是否有任何不清楚的地方。如果有任何错误请纠正我:)
本文内容由网友自发贡献，版权归原作者所有，本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容，请联系:hwhale#tublm.com(使用前将#替换为@)
