algorithm - 编程珠 - 随机选择算法

Question

Programming Pearls 第 1 版第 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 < N/2。

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

我知道 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/(N-M)

现在，如果 M < N/2，则该求和中的最后一个元素以 2 为界。 ((N/N/2) == 2))。它显然也是整个求和中最大的元素。所以如果最大的元素是两个picks，并且有M个元素相加，整个运行时间的EV就是2M以上。

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