抽样问题

需求:从正整数1-100中随机抽取20个数。

以下算法均来自与《编程珠玑》

1.精妙的算法,运用概率的知识。

或许你不理解rand()%(n-i)<m这一句,我开始也不理解,请教了高人之后才理解的,所以就写了这篇博客,以免忘了。

从n中选m个数,每个数被选中概率为m/n。

第一个数被选中的概率是m/n。

第二数被选中概率的计算如下:如果第一数被选中了,(m-1)/(n-1); 如果第一个数没有被选中,m/(n-1)。所以总体概率为m/n * (m-1)/(n-1) +(n-m)/n * m/(n-1) = m/n

以此类推。。。每个数被选中的概率都是m/n。

假设一个随机数生成器R,生成的数属于[0,Z-1],且生成每个数的概率相等。

对任意一个小于Z的数Q,那么R()<Q的概率即Q/Z。所以rand()%(n-i) < m 即表示m/n-i的概率,也就是当前数字被选中的概率。

严格来说,rand()%(n-i)并不是一个等概率生成器,因为rand()显然不是对每个i都是n-i的整数倍。

(以上解释出自肖微)

2.往一个初始为空的集合中插入随机整数,直到填入足够的整数。需要额外的m*size(int)的空间,最大的问题是需要查询重复元素。

3.弄乱n个元素,时间复杂度是O(m),但需要做交换操作。

发表评论

电子邮件地址不会被公开。 必填项已用*标注