小编mpm*_*mpm的帖子

编程珍珠第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选择现有元素的可能性将按比例增加.

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