在抽样的样本大小未知的情况下需要等概率选出一个数的时候推荐使用
原理:
遇到符合条件的数时选择的概率为1/n,n目前的元素个数,这样做每个数最终被选到的概率是相等的
证明:
客观来看
遇到第1个数时,第一个数被选择的概率为1/1
遇到第2个数时,第一个数被选择的概率为1/1*1/2=1/2,第二个数被选择的概率为1/2
遇到第3个数时,第一个数被选择的概率为1/1*1/2*2/3=1/2,第二个数被选择的概率为1/2*2/3=1/3,第三个数被选择的概率为1/3
推下去每个数被选择的概率都是一样的
在数组中等概率选择一个符合条件的数,例如有一个数组有10个元素:5,3,4,8,6,9,1,2,7,10;
随机选择一个数
直接用rand(),时间复杂度为O(1)
#includeusing namespace std; int main(){ int a[10]={5,3,4,8,6,9,1,2,7,10}; cout< 水塘抽样法O(n)
#includeusing namespace std; int main(){ int a[10]={5,3,4,8,6,9,1,2,7,10}; int select; int n=1; for(int i=0;i<10;i++){ if(rand()%n==0){ select=a[i]; n++; } } cout<
评论列表(0条)