《算法设计与分析》 第七章 随机算法及计算复杂性概要课件

第七章随机算法及NP完全问题7.1随机算法引言7.2随机算法的类型7.3随机数发生器7.4数值概率算法7.5舍伍德(Sherwood)算法7.6拉斯维加斯（LasVegas）算法7.7蒙特卡罗（MonteCarlo）算法7.8NP完全问题第七章随机算法及NP完全问题7.1随机算法引言17.1随机算法引言确定性的算法：算法的每一个计算步骤都是确定的，对于相同的输出，每一次执行过程都会产生相同的输出。随机算法：非形式描述随机算法为使用随机函数产生器的算法。算法中的一些判定依赖于随机函数产生器的输出。随机算法对于相同的输入，在不同的运行过程中会得到不同的输出。对于相同的输入，随机算法的执行时间也可能随不同的运行过程而不同。7.1随机算法引言确定性的算法：28.1随机算法引言随机算法的优点：1、执行时间和空间，小于同一问题的已知最好的确定性算法；2、实现比较简单，容易理解。很多确定性的算法，其性能很坏。可用随机选择的方法来改善算法的性能。某些方面可能不正确，对特定的输入，算法的每一次运行不一定得到相同结果。出现这种不正确的可能性很小，以致可以安全地不予理睬。8.1随机算法引言随机算法的优点：37.2随机算法的类型数值概率算法拉斯维加斯（LasVegas）算法蒙特卡罗（MonteCarlo）算法舍伍德（Sherwood）算法。7.2随机算法的类型数值概率算法47.2随机算法的类型1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度随着计算时间的增加而不断地提高。2、舍伍德（Sherwood）算法：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。7.2随机算法的类型1、数值概率算法：用于数值问题的求解。57.2随机算法的类型3、拉斯维加斯（LasVegas）算法：要么给出问题的正确答案，要么得不到答案。反复求解多次，可使失效的概率任意小。4、蒙特卡罗（MonteCarlo）算法：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意小。7.2随机算法的类型3、拉斯维加斯（LasVegas）算67.3随机数发生器产生随机数的公式：

产生0~65535的随机数序列，b、c、d为正整数，称为所产生的随机序列的种子。常数b、c，对所产生的随机序列的随机性能有很大的关系，b通常取一素数。7.3随机数发生器产生随机数的公式：77.3随机数发生器#define MULTIPLIER 0x015A4E35L;#define INCREMENT 1;staticunsignedlong seed;voidrandom_seed(unsignedlongd){if(d==0)seed=time(0);elseseed=d;}unsignedintrandom(unsignedlonglow,unsignedlonghigh){seed=MULTIPLIER*seed+INCREMENT;return((seed>>16)%(high–low)+low);}7.3随机数发生器#define MULTIPLIER 087.4数值概率算法例：用随机投点法计算值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为。所以当n足够大时，k与n之比就逼近这一概率。从而7.4数值概率算法例：用随机投点法计算值97.4数值概率算法publicdoubledarts(intn){//用随机投点法计算值intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/(double)n;}7.4数值概率算法publicdoubledarts(107.5舍伍德(Sherwood)算法一、确定性算法的平均运行时间TA(x)：确定性算法对输入实例的运行时间。Xn：规模为的所有输入实例全体。算法的平均运行时间：存在实例，。例：快速排序算法当输入数据均匀分布时，运行时间是。当输入数据按递增或递减顺序排列时，算法的运行时间变坏7.5舍伍德(Sherwood)算法一、确定性算法的平均运117.5舍伍德(Sherwood)算法二、舍伍德算法的基本思想消除不同输入实例对算法性能的影响，使随机算法对规模为的每一个实例，都有：三、期望运行时间：

当s(n)与相比很小可以忽略时，舍伍德算法有很好的性能。对所有输入实例而言，运行时间相对均匀。时间复杂性与确定性算法的时间复杂性相当.7.5舍伍德(Sherwood)算法二、舍伍德算法的基本思127.5舍伍德(Sherwood)算法随机快速排序算法算法9.1随机选择枢点的快速排序算法输入：数组A,数组元素的的起始位置low,终止位置high输出：按非降顺序排序的数组A

1.template<classType>2.voidquicksort_random(TypeA[],intlow,inthigh)3.{4.random_seed(0);/*选择系统当前时间作为随机数种子*/5.r_quicksort(A,low,high); /*递归调用随机快速排序算法*/6.}7.5舍伍德(Sherwood)算法随机快速排序算法137.5舍伍德(Sherwood)算法1.voidr_quicksort(TypeA[],intlow,inthigh)2.{3.intk;4.if(low<high){5.k=random(low,high);/*产生low到high之间的随机数k*/6.swap(A[low],A[k]);/*把元素A[k]交换到数组的第一个位置*/7.k=split(A,low,high); /*按元素A[low]把数组划分为两个*/8.r_quicksort(A,low,k-1); /*排序第一个子数组*/9.r_quicksort(A,k+1,high); /*排序第二个子数组*/10.}11.}算法的期望运行时间是。7.5舍伍德(Sherwood)算法1.voidr_q147.6拉斯维加斯（LasVegas）算法一、一般概念 拉斯维加斯算法有时运行成功，有时失败，需要反复运行同一实例，直到成功为止。 BOOLlas_vegas()：解问题的某个实例的代码段。运行成功返回true，否则返回false。 拉斯维加斯算法反复地运行下面的代码段： while(!las_vegas(P(x))); 直到运行成功返回为止。7.6拉斯维加斯（LasVegas）算法一、一般概念157.6拉斯维加斯（LasVegas）算法p(x)：对输入实例成功地运行las_vegas的概率若存在常数δ>0，使得对的所有实例p，都有p(x)>=δ，则失败的概率小于1-δ。连续运行k次，失败的概率降低为(1-δ)k。k充分大，(1-δ)k趋于0。7.6拉斯维加斯（LasVegas）算法p(x)：对输入167.6拉斯维加斯（LasVegas）算法例：识别重复元素考虑一个有n个数字的数组a[]，其中有n/2个不同的元素，其余元素是另一个元素的拷贝，即数组中共有（n/2）+1个不同的元素。问题是要识别重复的元素。确定性算法： 至少需要（n/2）+2个时间步。7.6拉斯维加斯（LasVegas）算法例：识别重复元素177.6拉斯维加斯（LasVegas）算法拉斯维加斯（LasVegas）算法intRepeatedElement(Typea[],intn){while(1){inti=random()%n+1;intj=random()%n+1;if((i!=j)&&(a[i]==a[j]))return(i);}}7.6拉斯维加斯（LasVegas）算法拉斯维加斯（La187.6拉斯维加斯（LasVegas）算法while循环则任何一次迭代中退出的概率为p=.当n≥10时，p≥1/5,则不退出的概率≤4/5。算法在前calogn(c为固定常数)次迭代内不退出的概率<(4/5)calogn=n-calog(4/5),若取c≥1/log(5/4),则其值<n-a,因此，算法在calogn次迭代以内终止的概率≥1-n-a。每次迭代花费O(1)的时间，算法的执行时间为O(logn)。7.6拉斯维加斯（LasVegas）算法while循环则197.7蒙特卡罗（MonteCarlo）算法蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。设p是一个实数，且1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。7.7蒙特卡罗（MonteCarlo）算法蒙特卡罗算法207.7蒙特卡罗（MonteCarlo）算法数组的主元素问题一、问题n个元素的数组A，A中元素x，若A中一半以上元素与x相同，称x是A的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每个元素和其它元素比较，并计数。如果计数值大于n/2，该元素就是的主元素。元素比较次数为。7.7蒙特卡罗（MonteCarlo）算法数组的主元素问217.7蒙特卡罗（MonteCarlo）算法三、蒙特卡罗算法1、随机选择元素A[i]进行测试，若返回true，A[i]就是主元素；否则不是主元素。7.7蒙特卡罗（MonteCarlo）算法三、蒙特卡罗算227.7蒙特卡罗（MonteCarlo）算法算法9.7求数组A的主元素输入：n个元素的数组A[]输出：数组A的主元素

BOOLmajority(TypeA[],Type&x,intn){inti,j,k; random_seed(0);i=random(0,n-1);k=0; for(j=0;j<n;j++) if(A[i]==A[j])k++; if(k>n/2){x=A[i];returnTRUE;}elsereturnFALSE;}7.7蒙特卡罗（MonteCarlo）算法算法9.7237.7蒙特卡罗（MonteCarlo）算法2、如果存在主元素，以大于1/2的概率返回true，小于1/2的概率返回false。连续运行k次，返回的概率减少为2-k，算法错误的概率为2-k。希望错误概率小于ε，则令：2-k=ε

k=log(1/ε)算法修改为：7.7蒙特卡罗（MonteCarlo）算法2、如果存在主247.7蒙特卡罗（MonteCarlo）算法BOOLmajority_monte(TypeA[],Type&x,intn,doublee){intt,s,i,j,k;BOOLflag=FALSE;random_seed(0);s=log(1/e);for(t=1;t<=s;t++){i=random(0,n-1);k=0;for(j=0;j<n;j++)if(A[i]==A[j])k++;if(k>n/2){x=A[i];flag=TRUE;break;}}returnflag;}算法的错误概率小于所给参数e。算法的运行时间为O(nlog(1/e))。7.7蒙特卡罗（MonteCarlo）算法BOOLma257.7蒙特卡罗（MonteCarlo）算法素数测试一、一般方法被测试的数除以2到的数，余数为0，是合数，否则是素数。二、蒙特卡罗算法7.7蒙特卡罗（MonteCarlo）算法素数测试26素数测试Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!-1(modn)。费尔马小定理：如果p是一个素数，且0<a<p，则ap-1(modp)。二次探测定理：如果p是一个素数，且0<x<p，则方程x21(modp)的解为x=1，power(inta,intp,intn){//计算apmodn，并实施对n的二次探测intx,result;if(p==0)result=1;else{x=power(a,p/2,n);//递归计算result=(x*x)%n;//二次探测if((result==1)&&(x!=1)&&(x!=n-1))composite=true;if((p%2)==1)//p是奇数result=(result*a)%n;}returnresult;}booleanprime(intn){//素数测试的蒙特卡罗算法rnd=newRandom();inta,result;composite=false;a=rnd.random(n-3)+2;result=power(a,n-1,n);if(composite||(result!=1))returnfalse;elsereturntrue;}算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。素数测试Wilson定理：对于给定的正整数n，判定n是一个素277.8NP难与NP完全问题一、易解的问题和难解的问题存在多项式时间算法的问题，称为易解的问题指数时间算法或排列时间算法的问题，称为难解的问题二、难解问题的计算相关性计算相关：某类问题可以归约为另一类问题计算相关的问题，若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找到多项式时间算法。7.8NP难与NP完全问题一、易解的问题和难解的问题287.8NP难与NP完全问题

P类和NP类问题定义12.1是问题的一个算法。如果在处理问题的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法是确定性的算法。定义12.2如果对某个判定问题，存在着一个非负整数k，对输入规模为n的实例，能够以O(nk)的时间运行一个确定性的算法，得到yes或no的答案，则该判定问题π是一个p类判定问题。7.8NP难与NP完全问题

P类和NP类问题定义12.1297.8NP难与NP完全问题

P类和NP类问题定义12.5如果对某个判定问题，存在着一个非负整数k，对输入规模为n的实例，能够以O(nk)的时间运行一个非确定性的算法，得到yes或no的答案，则该判定问题π是一个NP类判定问题。特性： 存在确定性的算法，能够以多项式时间，来检查和验证在推测阶段产生的答案。7.8NP难与NP完全问题

P类和NP类问题定义12.307.8NP难与NP完全问题

NP难问题NP难定义12.6令π是一个判定问题，如果对NP中的每一个问题π‘∈

NP，有，就说判定问题π是一个NP难题。7.8NP难与NP完全问题

NP难问题NP难317.8NP难与NP完全问题

NP完全问题NP完全问题定义12.7令π是一个判定问题，如果：(1)π∈

NP，并且：(2)对NP中的所有问题π‘∈

NP，都有； 则称判定问题π是NP完全的。7.8NP难与NP完全问题

NP完全问题NP完全问题327.8NP难与NP完全问题

NP难题和NP完全问题的差别π是NP完全问题，π‘是NP难题，则π必定在NP类中，而π‘不一定在NP类中。7.8NP难与NP完全问题

NP难题和NP完全问题的差别337.8NP难与NP完全问题

1、归约的传递性定理12.3令、和是三个判定问题，满足，及，则有。7.8NP难与NP完全问题

1、归约的传递性347.8NP难与NP完全问题

NP完全问题的特性定理12.4令和是NP中的两个问题，使得。如果是NP完全的，则也是NP完全的。7.8NP难与NP完全问题

NP完全问题的特性357.8NP难与NP完全问题

NP完全问题的证明：证明下面两件事情：(1)，并且：(2)存在一个NP完全问题，使得；7.8NP难与NP完全问题

NP完全问题的证明：367.8NP难与NP完全问题

定理12.5（Cook定理）可满足性问题SATISFIABILITY是NP完全的。Cook定理的意义：Cook定理给出了第一个NP完全问题，使得对任何问题，只要能够证明，并且SATISFIABILITY，那么，就是NP完全的7.8NP难与NP完全问题

定理12.5（Cook定理）可377.8NP难与NP完全问题

部分的NP完全问题树7.8NP难与NP完全问题

部分的NP完全问题树387.8NP难与NP完全问题

通常认为的P、NP、NPComplete、NPHard问题的关系：PNPNPCompleteNPHard7.8NP难与NP完全问题

通常认为的P、NP、NPCo397.8NP难与NP完全问题

NP完全问题的特性为：当且仅当所有其它NP完全问题可以在多项式时间内求解，该问题可以在多项式时间内求解。如果一个NP难问题可以在多项式时间内求解，则所有的NP完全问题都可以在多项式时间内求解。NP完全和NP难问题都不是多项式时间可解的。7.8NP难与NP完全问题

NP完全问题的特性为：当且仅当40第七章随机算法及NP完全问题7.1随机算法引言7.2随机算法的类型7.3随机数发生器7.4数值概率算法7.5舍伍德(Sherwood)算法7.6拉斯维加斯（LasVegas）算法7.7蒙特卡罗（MonteCarlo）算法7.8NP完全问题第七章随机算法及NP完全问题7.1随机算法引言417.1随机算法引言确定性的算法：算法的每一个计算步骤都是确定的，对于相同的输出，每一次执行过程都会产生相同的输出。随机算法：非形式描述随机算法为使用随机函数产生器的算法。算法中的一些判定依赖于随机函数产生器的输出。随机算法对于相同的输入，在不同的运行过程中会得到不同的输出。对于相同的输入，随机算法的执行时间也可能随不同的运行过程而不同。7.1随机算法引言确定性的算法：428.1随机算法引言随机算法的优点：1、执行时间和空间，小于同一问题的已知最好的确定性算法；2、实现比较简单，容易理解。很多确定性的算法，其性能很坏。可用随机选择的方法来改善算法的性能。某些方面可能不正确，对特定的输入，算法的每一次运行不一定得到相同结果。出现这种不正确的可能性很小，以致可以安全地不予理睬。8.1随机算法引言随机算法的优点：437.2随机算法的类型数值概率算法拉斯维加斯（LasVegas）算法蒙特卡罗（MonteCarlo）算法舍伍德（Sherwood）算法。7.2随机算法的类型数值概率算法447.2随机算法的类型1、数值概率算法：用于数值问题的求解。所得到的解几乎都是近似解，近似解的精度随着计算时间的增加而不断地提高。2、舍伍德（Sherwood）算法：很多具有很好的平均运行时间的确定性算法，在最坏的情况下性能很坏。引入随机性加以改造，可以消除或减少一般情况和最坏情况的差别。7.2随机算法的类型1、数值概率算法：用于数值问题的求解。457.2随机算法的类型3、拉斯维加斯（LasVegas）算法：要么给出问题的正确答案，要么得不到答案。反复求解多次，可使失效的概率任意小。4、蒙特卡罗（MonteCarlo）算法：总能得到问题的答案，偶然产生不正确的答案。重复运行，每一次都进行随机选择，可使不正确答案的概率变得任意小。7.2随机算法的类型3、拉斯维加斯（LasVegas）算467.3随机数发生器产生随机数的公式：

产生0~65535的随机数序列，b、c、d为正整数，称为所产生的随机序列的种子。常数b、c，对所产生的随机序列的随机性能有很大的关系，b通常取一素数。7.3随机数发生器产生随机数的公式：477.3随机数发生器#define MULTIPLIER 0x015A4E35L;#define INCREMENT 1;staticunsignedlong seed;voidrandom_seed(unsignedlongd){if(d==0)seed=time(0);elseseed=d;}unsignedintrandom(unsignedlonglow,unsignedlonghigh){seed=MULTIPLIER*seed+INCREMENT;return((seed>>16)%(high–low)+low);}7.3随机数发生器#define MULTIPLIER 0487.4数值概率算法例：用随机投点法计算值设有一半径为r的圆及其外切四边形。向该正方形随机地投掷n个点。设落入圆内的点数为k。由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为。所以当n足够大时，k与n之比就逼近这一概率。从而7.4数值概率算法例：用随机投点法计算值497.4数值概率算法publicdoubledarts(intn){//用随机投点法计算值intk=0;for(inti=1;i<=n;i++){doublex=dart.fRandom();doubley=dart.fRandom();if((x*x+y*y)<=1)k++;}return4*k/(double)n;}7.4数值概率算法publicdoubledarts(507.5舍伍德(Sherwood)算法一、确定性算法的平均运行时间TA(x)：确定性算法对输入实例的运行时间。Xn：规模为的所有输入实例全体。算法的平均运行时间：存在实例，。例：快速排序算法当输入数据均匀分布时，运行时间是。当输入数据按递增或递减顺序排列时，算法的运行时间变坏7.5舍伍德(Sherwood)算法一、确定性算法的平均运517.5舍伍德(Sherwood)算法二、舍伍德算法的基本思想消除不同输入实例对算法性能的影响，使随机算法对规模为的每一个实例，都有：三、期望运行时间：

当s(n)与相比很小可以忽略时，舍伍德算法有很好的性能。对所有输入实例而言，运行时间相对均匀。时间复杂性与确定性算法的时间复杂性相当.7.5舍伍德(Sherwood)算法二、舍伍德算法的基本思527.5舍伍德(Sherwood)算法随机快速排序算法算法9.1随机选择枢点的快速排序算法输入：数组A,数组元素的的起始位置low,终止位置high输出：按非降顺序排序的数组A

1.template<classType>2.voidquicksort_random(TypeA[],intlow,inthigh)3.{4.random_seed(0);/*选择系统当前时间作为随机数种子*/5.r_quicksort(A,low,high); /*递归调用随机快速排序算法*/6.}7.5舍伍德(Sherwood)算法随机快速排序算法537.5舍伍德(Sherwood)算法1.voidr_quicksort(TypeA[],intlow,inthigh)2.{3.intk;4.if(low<high){5.k=random(low,high);/*产生low到high之间的随机数k*/6.swap(A[low],A[k]);/*把元素A[k]交换到数组的第一个位置*/7.k=split(A,low,high); /*按元素A[low]把数组划分为两个*/8.r_quicksort(A,low,k-1); /*排序第一个子数组*/9.r_quicksort(A,k+1,high); /*排序第二个子数组*/10.}11.}算法的期望运行时间是。7.5舍伍德(Sherwood)算法1.voidr_q547.6拉斯维加斯（LasVegas）算法一、一般概念 拉斯维加斯算法有时运行成功，有时失败，需要反复运行同一实例，直到成功为止。 BOOLlas_vegas()：解问题的某个实例的代码段。运行成功返回true，否则返回false。 拉斯维加斯算法反复地运行下面的代码段： while(!las_vegas(P(x))); 直到运行成功返回为止。7.6拉斯维加斯（LasVegas）算法一、一般概念557.6拉斯维加斯（LasVegas）算法p(x)：对输入实例成功地运行las_vegas的概率若存在常数δ>0，使得对的所有实例p，都有p(x)>=δ，则失败的概率小于1-δ。连续运行k次，失败的概率降低为(1-δ)k。k充分大，(1-δ)k趋于0。7.6拉斯维加斯（LasVegas）算法p(x)：对输入567.6拉斯维加斯（LasVegas）算法例：识别重复元素考虑一个有n个数字的数组a[]，其中有n/2个不同的元素，其余元素是另一个元素的拷贝，即数组中共有（n/2）+1个不同的元素。问题是要识别重复的元素。确定性算法： 至少需要（n/2）+2个时间步。7.6拉斯维加斯（LasVegas）算法例：识别重复元素577.6拉斯维加斯（LasVegas）算法拉斯维加斯（LasVegas）算法intRepeatedElement(Typea[],intn){while(1){inti=random()%n+1;intj=random()%n+1;if((i!=j)&&(a[i]==a[j]))return(i);}}7.6拉斯维加斯（LasVegas）算法拉斯维加斯（La587.6拉斯维加斯（LasVegas）算法while循环则任何一次迭代中退出的概率为p=.当n≥10时，p≥1/5,则不退出的概率≤4/5。算法在前calogn(c为固定常数)次迭代内不退出的概率<(4/5)calogn=n-calog(4/5),若取c≥1/log(5/4),则其值<n-a,因此，算法在calogn次迭代以内终止的概率≥1-n-a。每次迭代花费O(1)的时间，算法的执行时间为O(logn)。7.6拉斯维加斯（LasVegas）算法while循环则597.7蒙特卡罗（MonteCarlo）算法蒙特卡罗算法则在一般情况下可以保证对问题的所有实例都以高概率给出正确解，但是通常无法判定一个具体解是否正确。设p是一个实数，且1/2<p<1。如果一个蒙特卡罗算法对于问题的任一实例得到正确解的概率不小于p，则称该蒙特卡罗算法是p正确的，且称p-1/2是该算法的优势。如果对于同一实例，蒙特卡罗算法不会给出2个不同的正确解答，则称该蒙特卡罗算法是一致的。7.7蒙特卡罗（MonteCarlo）算法蒙特卡罗算法607.7蒙特卡罗（MonteCarlo）算法数组的主元素问题一、问题n个元素的数组A，A中元素x，若A中一半以上元素与x相同，称x是A的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每个元素和其它元素比较，并计数。如果计数值大于n/2，该元素就是的主元素。元素比较次数为。7.7蒙特卡罗（MonteCarlo）算法数组的主元素问617.7蒙特卡罗（MonteCarlo）算法三、蒙特卡罗算法1、随机选择元素A[i]进行测试，若返回true，A[i]就是主元素；否则不是主元素。7.7蒙特卡罗（MonteCarlo）算法三、蒙特卡罗算627.7蒙特卡罗（MonteCarlo）算法算法9.7求数组A的主元素输入：n个元素的数组A[]输出：数组A的主元素

BOOLmajority(TypeA[],Type&x,intn){inti,j,k; random_seed(0);i=random(0,n-1);k=0; for(j=0;j<n;j++) if(A[i]==A[j])k++; if(k>n/2){x=A[i];returnTRUE;}elsereturnFALSE;}7.7蒙特卡罗（MonteCarlo）算法算法9.7637.7蒙特卡罗（MonteCarlo）算法2、如果存在主元素，以大于1/2的概率返回true，小于1/2的概率返回false。连续运行k次，返回的概率减少为2-k，算法错误的概率为2-k。希望错误概率小于ε，则令：2-k=ε

k=log(1/ε)算法修改为：7.7蒙特卡罗（MonteCarlo）算法2、如果存在主647.7蒙特卡罗（MonteCarlo）算法BOOLmajority_monte(TypeA[],Type&x,intn,doublee){intt,s,i,j,k;BOOLflag=FALSE;random_seed(0);s=log(1/e);for(t=1;t<=s;t++){i=random(0,n-1);k=0;for(j=0;j<n;j++)if(A[i]==A[j])k++;if(k>n/2){x=A[i];flag=TRUE;break;}}returnflag;}算法的错误概率小于所给参数e。算法的运行时间为O(nlog(1/e))。7.7蒙特卡罗（MonteCarlo）算法BOOLma657.7蒙特卡罗（MonteCarlo）算法素数测试一、一般方法被测试的数除以2到的数，余数为0，是合数，否则是素数。二、蒙特卡罗算法7.7蒙特卡罗（MonteCarlo）算法素数测试66素数测试Wilson定理：对于给定的正整数n，判定n是一个素数的充要条件是(n-1)!-1(modn)。费尔马小定理：如果p是一个素数，且0<a<p，则ap-1(modp)。二次探测定理：如果p是一个素数，且0<x<p，则方程x21(modp)的解为x=1，power(inta,intp,intn){//计算apmodn，并实施对n的二次探测intx,result;if(p==0)result=1;else{x=power(a,p/2,n);//递归计算result=(x*x)%n;//二次探测if((result==1)&&(x!=1)&&(x!=n-1))composite=true;if((p%2)==1)//p是奇数result=(result*a)%n;}returnresult;}booleanprime(intn){//素数测试的蒙特卡罗算法rnd=newRandom();inta,result;composite=false;a=rnd.random(n-3)+2;result=power(a,n-1,n);if(composite||(result!=1))returnfalse;elsereturntrue;}算法prime是一个偏假3/4正确的蒙特卡罗算法。通过多次重复调用错误概率不超过(1/4)k。这是一个很保守的估计，实际使用的效果要好得多。素数测试Wilson定理：对于给定的正整数n，判定n是一个素677.8NP难与NP完全问题一、易解的问题和难解的问题存在多项式时间算法的问题，称为易解的问题指数时间算法或排列时间算法的问题，称为难解的问题二、难解问题的计算相关性计算相关：某类问题可以归约为另一类问题计算相关的问题，若它们之一可用多项式时间求解，则其它同类问题也可用多项式时间求解；若它们之一肯定不存在多项式时间算法，则同类的其它问题，也肯定不会找到多项式时间算法。7.8NP难与NP完全问题一、易解的问题和难解的问题687.8NP难与NP完全问题

P类和NP类问题定义12.1是问题的一个算法。如果在处理问题的实例时，在算法的整个执行过程中，每一步只有一个确定的选择，就说算法是