编程珍珠 - 随机选择算法

Question

编程珍珠第1版提出了这种算法,用于从N个整数的群体中选择M个等概率的随机元素.

InitToEmpty
Size := 0
While Size < M do
  T := RandInt(1,N)
  if not Member(T)    
     Insert(T)
     Size := Size + 1

据称,只要M <N/2,预期会员测试的数量小于2M.

我想知道如何证明它,但我的算法分析背景让我失望.

我理解M越接近N,程序将花费的时间越长,因为结果集将具有更多元素,并且RandInt选择现有元素的可能性将按比例增加.

你能帮我弄清楚这个证明吗？

Answer 1

我不是数学奇才，但我会粗略地尝试一下。但这并不能保证是正确的。

对于 M 的每个附加成员，您选择一个数字，查看它是否存在，如果存在则添加它。否则，你再试一次。尝试某件事直到成功称为几何概率分布。

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/ (NM)

现在，如果 M < N/2，则该求和中的最后一个元素的边界为 2。((N/N/2) == 2))。它显然也是整个求和中最大的元素。因此，如果最大的元素是两个选择，并且有 M 个元素被求和，则整个运行时间的 EV 上限为 2M。

问我是否有任何不清楚的地方。如果有任何错误请纠正我:)