第九章 概率算法 2021/2/21 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 1 第九章 概率算法
概率计算 ■概率计算就是在算法中可采用随机选择计算的 步骤、元素或参数等 ■它的基本特征是计算具有不确定性 ■它的解也不一定是最优解。 ■它在很大程度上能降低算法的复杂度。 在非标准算法中普遍了应用概率方法,主要有: ■(1)直接用概率进行数值计算 ■(2)用概率/随机进行选择; ■(3)利用概率加速搜索或避免陷于局部最优 2021/221 计算机算法设计与分析 2
2021/2/21 计算机算法设计与分析 2 概率计算 ◼ 概率计算就是在算法中可采用随机选择计算的 步骤、元素或参数等。 ◼ 它的基本特征是计算具有不确定性。 ◼ 它的解也不一定是最优解。 ◼ 它在很大程度上能降低算法的复杂度。 ◼ 在非标准算法中普遍了应用概率方法，主要有： ◼ (1)直接用概率进行数值计算； ◼ (2)用概率/随机进行选择； ◼ (3)利用概率加速搜索或避免陷于局部最优
直接用概率进行数值计算 ■设fx)是[0,1上的连续函数, 求I可代xdx。 y=f(x) ■假设向单位正方形内随机 投入n个点(x2y,若有m个 G 点落入G中,则I≈m/n double Darts (int n) double x, y; int k=0 static Random number dart for(int F1; K<=n; i++)ix-dart. randome y-dart. fRandomO; if (<=f(x)k++, return k/double(n);) 2021/22 计算机算法设计与分析 3
2021/2/21 计算机算法设计与分析 3 直接用概率进行数值计算 ◼ 设f(x)是[0, 1]上的连续函数， 求I =∫ f(x)dx 0 1 。 y = f(x) G ◼ 假设向单位正方形内随机 投入n个点(xi , yi )，若有m个 点落入G中，则I≈m/n。 ◼ double Darts (int n) {double x, y; int k = 0; ◼ static RandomNumber dart; ◼ for (int i=1; i<=n; i++) {x=dart.fRandom(); ◼ y=dart.fRandom(); if (y<=f(x)) k++;} ◼ return k/double(n); }
划分基准的随机选择 ■在快速排序算法中,若用拟中位数作为划分标 准,可保证在线性时间内完成。但是确定拟中 位数要付出额外开销。若选用第一个元素为划 分基准,最坏时的时间复杂性为O(n2 ■若在算法中采用随机选择一个元素作为划分标 准,便可既保证算法的线性时间平均性能,又 避免了计算拟中位数的麻烦 也可先对数组进行“洗牌”,然后再进行确定 的排序算法。这样依然可取得同样的效果。 2021/221 计算机算法设计与分析
2021/2/21 计算机算法设计与分析 4 划分基准的随机选择 ◼ 在快速排序算法中，若用拟中位数作为划分标 准，可保证在线性时间内完成。但是确定拟中 位数要付出额外开销。若选用第一个元素为划 分基准，最坏时的时间复杂性为O(n2 )。 ◼ 若在算法中采用随机选择一个元素作为划分标 准，便可既保证算法的线性时间平均性能，又 避免了计算拟中位数的麻烦。 ◼ 也可先对数组进行“洗牌”，然后再进行确定 的排序算法。这样依然可取得同样的效果
“洗牌”后的快速排序 void shuffle( Type a[,intn){/随机洗牌算法 static Random number md for(int 1=1; 1<n; i++)i int j=md Random(n-i+1)+i Swap(all, alD;i) Void Quiksort By Shuffle(Type all, int n)i Shuffle(a,n);∥.数组a洗牌 Quiksort(a, n ;) 2021/22 计算机算法设计与分析 5
2021/2/21 计算机算法设计与分析 5 “洗牌”后的快速排序 ◼ void Shuffle(Type a[], int n) { //随机洗牌算法 ◼ static RandomNumber md; ◼ for (int i = 1; i < n; i++) { ◼ int j = md.Random(n – i + 1) + i; ◼ Swap(a[i], a[j]); }} ◼ Void QuiksortByShuffle(Type a[], int n) { ◼ Shuffle(a, n); //将数组a洗牌 ◼ Quiksort(a, n); }
随机抽样 ■在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是否 为素数