- 1、本文档共38页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
[工学]概率算法
计算机算法设计与分析 第九章概率算法 概率计算 概率计算就是在算法中可采用随机选择计算的步骤、元素或参数等。 它的基本特征是计算具有不确定性。 它的解也不一定是最优解。 它在很大程度上能降低算法的复杂度。 在非标准算法中普遍了应用概率方法,主要有: (1)直接用概率进行数值计算; (2)用概率/随机进行选择; (3)利用概率加速有哪些信誉好的足球投注网站或避免陷于局部最优。 直接用概率进行数值计算 设f(x)是[0, 1]上的连续函数,求I =∫ f(x)dx。 划分基准的随机选择 在快速排序算法中,若用拟中位数作为划分标准,可保证在线性时间内完成。但是确定拟中位数要付出额外开销。若选用第一个元素为划分基准,最坏时的时间复杂性为O(n2)。 若在算法中采用随机选择一个元素作为划分标准,便可既保证算法的线性时间平均性能,又避免了计算拟中位数的麻烦。 也可先对数组进行“洗牌”,然后再进行确定的排序算法。这样依然可取得同样的效果。 “洗牌”后的快速排序 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(0m≤n)个无重复的元素。为简单起见,假定所有元素的值都位于1至n之间。 随机抽样 我们采用下面的方法进行选择: 1、首先将n个元素都标记为“未选择”; 2、重复下列步骤直到抽取了m个不同的元素 ⑴产生一个1至n间的随机数r; ⑵如果r标记为“未选择”,将它标记为“已选择”,并加入到抽样中。 随机抽样 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的因子。它虽然没有降低算法的复杂度,但实际运行速度比前者要快得多。 概率算法,保证一定概率的前提下简单判断。 Fermat素数测试法 Fermat定理: 若p是素数,则对任意整数a,gcd(a, p) = 1,则有ap–1≡1 (mod p)。 显然,对素数p有pp–1 ≡1 (mod p)。 对于一般的整数n,满足nn–1≡1 (mod n)的数目很少。满足的称为伪素数。 就用是否满足nn–1≡1 (mod n)来判断n是否为素数。 Fermat素数测试法 Bool Fermat_Prime(int n) { a = 2; power = n – 1; other = 1; while(power 1) { if (power % 2 = = 1) {other *= a; other %= n;} power /= 2; a = a * a % n;} if (a * other % n == 1) return True; return False; } 合数的见证者 设n为测试的自然数,不妨设n是大于2的奇数,则有n – 1 = 2im,其中i是非负整数,m是正奇数。取一自然数b,1 b n,记W(b)为条件: ① bn–1 ≠ 1 (mod n) 或 ②?i,使得m = (n–1)/2i 且 1 gcd(bm–1, n) b。 若①或②中有一个为真,就认为W(b)满足,则n必定是合数,我们称b是n为合数的见证者。 若n有见证者,则n必定为合数。 合数的见证者多于一半 Miller已经证明,存在常数c,使得当n为合数时,在[1, c(log n)2]范围内有见证者。 Miller-Rabin素数判定概率算法 Bool Miller_Rabin_Prime(int n){ b[1 .. m] = Ra
文档评论(0)