随机抽样 ■在n个元素的集合中随机抽取m(0<m≤n) 个无重复的元素。为简单起见,假定所 有元素的值都位于1至n之间。 2021/221 计算机算法设计与分析 6
2021/2/21 计算机算法设计与分析 6 随机抽样 ◼ 在n个元素的集合中随机抽取m(0<m≤n) 个无重复的元素。为简单起见，假定所 有元素的值都位于1至n之间
随机抽样 ■我们采用下面的方法进行选择 ■1、首先将n个元素都标记为“未选择”; ■2、重复下列步骤直到抽取了m个不同的 元素 (1)产生一个1至n间的随机数r; ■(2)如果r标记为“未选择”,将它标记为 已选择”,并加入到抽样中。 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 7 随机抽样 ◼ 我们采用下面的方法进行选择： ◼ 1、首先将n个元素都标记为“未选择”； ◼ 2、重复下列步骤直到抽取了m个不同的 元素 ◼ ⑴产生一个1至n间的随机数r； ◼ ⑵如果r标记为“未选择”，将它标记为 “已选择”，并加入到抽样中
随机抽样 a int Random Sampling(s[n alm], m)t mark[1.n]-=False; count=0 while(count < m) random (1, n) if(markr]== false)& count++ A[count]SIr markr]=True,))) 2021/22 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 8 随机抽样 ◼ int RandomSampling(S[n], A[m], m) { ◼ mark[1..n] = False; count=0; ◼ while(count < m) { ◼ r = random(1, n); ◼ if (mark[r] == False) { ◼ count++; ◼ A[count]=S[r]; ◼ mark[r]=True; }}}
判定素数的概率算法 ■判定自然数是否是素数,不仅有重要理论意义, 而且在密码学中具有重要实用价值。 ■最简单的素数判定方法是依次测定从2到n中 是否存在n的因子,该算法的复杂度为O(n)。 ■筛法:将小于n的合数预先筛掉,而不用判断 其是否为n的因子。它虽然没有降低算法的复 杂度,但实际运行速度比前者要快得多 ■概率算法,保证一定概率的前提下简单判断 2021/22 计算机算法设计与分析 9
2021/2/21 计算机算法设计与分析 9 判定素数的概率算法 ◼ 判定自然数是否是素数，不仅有重要理论意义， 而且在密码学中具有重要实用价值。 ◼ 最简单的素数判定方法是依次测定从2到n ½ 中 是否存在n的因子，该算法的复杂度为O(n ½ )。 ◼ 筛法：将小于n的合数预先筛掉，而不用判断 其是否为n的因子。它虽然没有降低算法的复 杂度，但实际运行速度比前者要快得多。 ◼ 概率算法，保证一定概率的前提下简单判断
Fermat.素数测试法 Fermat定理:若p是素数,则对任意整 数a,gcod(a,p)=1,则有ap1=1(mdp 显然,对素数p有pp1=1(modp) 对于一般的整数n,满足nl=l(modn)的 数目很少。满足的称为伪素数 就用是否满足n-l=1(mdn)来判断n是否 为素数。 2021/221 计算机算法设计与分析 10
2021/2/21 计算机算法设计与分析 10 Fermat素数测试法 ◼ Fermat定理： 若p是素数，则对任意整 数a，gcd(a, p) = 1，则有a p–1≡1 (mod p)。 ◼ 显然，对素数p有p p–1 ≡1 (mod p)。 ◼ 对于一般的整数n，满足n n–1≡1 (mod n)的 数目很少。满足的称为伪素数。 ◼ 就用是否满足n n–1≡1 (mod n)来判断n是否 为素数