《算法設(shè)計與分析》 第七章 隨機(jī)算法及計算復(fù)雜性概要課件

第七章隨機(jī)算法及NP完全問題7.1隨機(jī)算法引言7.2隨機(jī)算法的類型7.3隨機(jī)數(shù)發(fā)生器7.4數(shù)值概率算法7.5舍伍德(Sherwood)算法7.6拉斯維加斯（LasVegas）算法7.7蒙特卡羅（MonteCarlo）算法7.8NP完全問題第七章隨機(jī)算法及NP完全問題7.1隨機(jī)算法引言17.1隨機(jī)算法引言確定性的算法：算法的每一個計算步驟都是確定的，對于相同的輸出，每一次執(zhí)行過程都會產(chǎn)生相同的輸出。隨機(jī)算法：非形式描述隨機(jī)算法為使用隨機(jī)函數(shù)產(chǎn)生器的算法。算法中的一些判定依賴于隨機(jī)函數(shù)產(chǎn)生器的輸出。隨機(jī)算法對于相同的輸入，在不同的運行過程中會得到不同的輸出。對于相同的輸入，隨機(jī)算法的執(zhí)行時間也可能隨不同的運行過程而不同。7.1隨機(jī)算法引言確定性的算法：28.1隨機(jī)算法引言隨機(jī)算法的優(yōu)點：1、執(zhí)行時間和空間，小于同一問題的已知最好的確定性算法；2、實現(xiàn)比較簡單，容易理解。很多確定性的算法，其性能很壞。可用隨機(jī)選擇的方法來改善算法的性能。某些方面可能不正確，對特定的輸入，算法的每一次運行不一定得到相同結(jié)果。出現(xiàn)這種不正確的可能性很小，以致可以安全地不予理睬。8.1隨機(jī)算法引言隨機(jī)算法的優(yōu)點：37.2隨機(jī)算法的類型數(shù)值概率算法拉斯維加斯（LasVegas）算法蒙特卡羅（MonteCarlo）算法舍伍德（Sherwood）算法。7.2隨機(jī)算法的類型數(shù)值概率算法47.2隨機(jī)算法的類型1、數(shù)值概率算法：用于數(shù)值問題的求解。所得到的解幾乎都是近似解，近似解的精度隨著計算時間的增加而不斷地提高。2、舍伍德（Sherwood）算法：很多具有很好的平均運行時間的確定性算法，在最壞的情況下性能很壞。引入隨機(jī)性加以改造，可以消除或減少一般情況和最壞情況的差別。7.2隨機(jī)算法的類型1、數(shù)值概率算法：用于數(shù)值問題的求解。57.2隨機(jī)算法的類型3、拉斯維加斯（LasVegas）算法：要么給出問題的正確答案，要么得不到答案。反復(fù)求解多次，可使失效的概率任意小。4、蒙特卡羅（MonteCarlo）算法：總能得到問題的答案，偶然產(chǎn)生不正確的答案。重復(fù)運行，每一次都進(jìn)行隨機(jī)選擇，可使不正確答案的概率變得任意小。7.2隨機(jī)算法的類型3、拉斯維加斯（LasVegas）算67.3隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)的公式：

產(chǎn)生0~65535的隨機(jī)數(shù)序列，b、c、d為正整數(shù)，稱為所產(chǎn)生的隨機(jī)序列的種子。常數(shù)b、c，對所產(chǎn)生的隨機(jī)序列的隨機(jī)性能有很大的關(guān)系，b通常取一素數(shù)。7.3隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)的公式：77.3隨機(jī)數(shù)發(fā)生器#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隨機(jī)數(shù)發(fā)生器#define MULTIPLIER 087.4數(shù)值概率算法例：用隨機(jī)投點法計算值設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機(jī)地投擲n個點。設(shè)落入圓內(nèi)的點數(shù)為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為。所以當(dāng)n足夠大時，k與n之比就逼近這一概率。從而7.4數(shù)值概率算法例：用隨機(jī)投點法計算值97.4數(shù)值概率算法publicdoubledarts(intn){//用隨機(jī)投點法計算值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數(shù)值概率算法publicdoubledarts(107.5舍伍德(Sherwood)算法一、確定性算法的平均運行時間TA(x)：確定性算法對輸入實例的運行時間。Xn：規(guī)模為的所有輸入實例全體。算法的平均運行時間：存在實例，。例：快速排序算法當(dāng)輸入數(shù)據(jù)均勻分布時，運行時間是。當(dāng)輸入數(shù)據(jù)按遞增或遞減順序排列時，算法的運行時間變壞7.5舍伍德(Sherwood)算法一、確定性算法的平均運117.5舍伍德(Sherwood)算法二、舍伍德算法的基本思想消除不同輸入實例對算法性能的影響，使隨機(jī)算法對規(guī)模為的每一個實例，都有：三、期望運行時間：

當(dāng)s(n)與相比很小可以忽略時，舍伍德算法有很好的性能。對所有輸入實例而言，運行時間相對均勻。時間復(fù)雜性與確定性算法的時間復(fù)雜性相當(dāng).7.5舍伍德(Sherwood)算法二、舍伍德算法的基本思127.5舍伍德(Sherwood)算法隨機(jī)快速排序算法算法9.1隨機(jī)選擇樞點的快速排序算法輸入：數(shù)組A,數(shù)組元素的的起始位置low,終止位置high輸出：按非降順序排序的數(shù)組A

1.template<classType>2.voidquicksort_random(TypeA[],intlow,inthigh)3.{4.random_seed(0);/*選擇系統(tǒng)當(dāng)前時間作為隨機(jī)數(shù)種子*/5.r_quicksort(A,low,high); /*遞歸調(diào)用隨機(jī)快速排序算法*/6.}7.5舍伍德(Sherwood)算法隨機(jī)快速排序算法137.5舍伍德(Sherwood)算法1.voidr_quicksort(TypeA[],intlow,inthigh)2.{3.intk;4.if(low<high){5.k=random(low,high);/*產(chǎn)生low到high之間的隨機(jī)數(shù)k*/6.swap(A[low],A[k]);/*把元素A[k]交換到數(shù)組的第一個位置*/7.k=split(A,low,high); /*按元素A[low]把數(shù)組劃分為兩個*/8.r_quicksort(A,low,k-1); /*排序第一個子數(shù)組*/9.r_quicksort(A,k+1,high); /*排序第二個子數(shù)組*/10.}11.}算法的期望運行時間是。7.5舍伍德(Sherwood)算法1.voidr_q147.6拉斯維加斯（LasVegas）算法一、一般概念 拉斯維加斯算法有時運行成功，有時失敗，需要反復(fù)運行同一實例，直到成功為止。 BOOLlas_vegas()：解問題的某個實例的代碼段。運行成功返回true，否則返回false。 拉斯維加斯算法反復(fù)地運行下面的代碼段： while(!las_vegas(P(x))); 直到運行成功返回為止。7.6拉斯維加斯（LasVegas）算法一、一般概念157.6拉斯維加斯（LasVegas）算法p(x)：對輸入實例成功地運行l(wèi)as_vegas的概率若存在常數(shù)δ>0，使得對的所有實例p，都有p(x)>=δ，則失敗的概率小于1-δ。連續(xù)運行k次，失敗的概率降低為(1-δ)k。k充分大，(1-δ)k趨于0。7.6拉斯維加斯（LasVegas）算法p(x)：對輸入167.6拉斯維加斯（LasVegas）算法例：識別重復(fù)元素考慮一個有n個數(shù)字的數(shù)組a[]，其中有n/2個不同的元素，其余元素是另一個元素的拷貝，即數(shù)組中共有（n/2）+1個不同的元素。問題是要識別重復(fù)的元素。確定性算法： 至少需要（n/2）+2個時間步。7.6拉斯維加斯（LasVegas）算法例：識別重復(fù)元素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循環(huán)則任何一次迭代中退出的概率為p=.當(dāng)n≥10時，p≥1/5,則不退出的概率≤4/5。算法在前calogn(c為固定常數(shù))次迭代內(nèi)不退出的概率<(4/5)calogn=n-calog(4/5),若取c≥1/log(5/4),則其值<n-a,因此，算法在calogn次迭代以內(nèi)終止的概率≥1-n-a。每次迭代花費O(1)的時間，算法的執(zhí)行時間為O(logn)。7.6拉斯維加斯（LasVegas）算法while循環(huán)則197.7蒙特卡羅（MonteCarlo）算法蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。設(shè)p是一個實數(shù)，且1/2<p<1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢。如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。7.7蒙特卡羅（MonteCarlo）算法蒙特卡羅算法207.7蒙特卡羅（MonteCarlo）算法數(shù)組的主元素問題一、問題n個元素的數(shù)組A，A中元素x，若A中一半以上元素與x相同，稱x是A的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每個元素和其它元素比較，并計數(shù)。如果計數(shù)值大于n/2，該元素就是的主元素。元素比較次數(shù)為。7.7蒙特卡羅（MonteCarlo）算法數(shù)組的主元素問217.7蒙特卡羅（MonteCarlo）算法三、蒙特卡羅算法1、隨機(jī)選擇元素A[i]進(jìn)行測試，若返回true，A[i]就是主元素；否則不是主元素。7.7蒙特卡羅（MonteCarlo）算法三、蒙特卡羅算227.7蒙特卡羅（MonteCarlo）算法算法9.7求數(shù)組A的主元素輸入：n個元素的數(shù)組A[]輸出：數(shù)組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。連續(xù)運行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;}算法的錯誤概率小于所給參數(shù)e。算法的運行時間為O(nlog(1/e))。7.7蒙特卡羅（MonteCarlo）算法BOOLma257.7蒙特卡羅（MonteCarlo）算法素數(shù)測試一、一般方法被測試的數(shù)除以2到的數(shù)，余數(shù)為0，是合數(shù)，否則是素數(shù)。二、蒙特卡羅算法7.7蒙特卡羅（MonteCarlo）算法素數(shù)測試26素數(shù)測試Wilson定理：對于給定的正整數(shù)n，判定n是一個素數(shù)的充要條件是(n-1)!-1(modn)。費爾馬小定理：如果p是一個素數(shù)，且0<a<p，則ap-1(modp)。二次探測定理：如果p是一個素數(shù)，且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是奇數(shù)result=(result*a)%n;}returnresult;}booleanprime(intn){//素數(shù)測試的蒙特卡羅算法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正確的蒙特卡羅算法。通過多次重復(fù)調(diào)用錯誤概率不超過(1/4)k。這是一個很保守的估計，實際使用的效果要好得多。素數(shù)測試Wilson定理：對于給定的正整數(shù)n，判定n是一個素277.8NP難與NP完全問題一、易解的問題和難解的問題存在多項式時間算法的問題，稱為易解的問題指數(shù)時間算法或排列時間算法的問題，稱為難解的問題二、難解問題的計算相關(guān)性計算相關(guān)：某類問題可以歸約為另一類問題計算相關(guān)的問題，若它們之一可用多項式時間求解，則其它同類問題也可用多項式時間求解；若它們之一肯定不存在多項式時間算法，則同類的其它問題，也肯定不會找到多項式時間算法。7.8NP難與NP完全問題一、易解的問題和難解的問題287.8NP難與NP完全問題

P類和NP類問題定義12.1是問題的一個算法。如果在處理問題的實例時，在算法的整個執(zhí)行過程中，每一步只有一個確定的選擇，就說算法是確定性的算法。定義12.2如果對某個判定問題，存在著一個非負(fù)整數(shù)k，對輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一個確定性的算法，得到y(tǒng)es或no的答案，則該判定問題π是一個p類判定問題。7.8NP難與NP完全問題

P類和NP類問題定義12.1297.8NP難與NP完全問題

P類和NP類問題定義12.5如果對某個判定問題，存在著一個非負(fù)整數(shù)k，對輸入規(guī)模為n的實例，能夠以O(shè)(nk)的時間運行一個非確定性的算法，得到y(tǒng)es或no的答案，則該判定問題π是一個NP類判定問題。特性： 存在確定性的算法，能夠以多項式時間，來檢查和驗證在推測階段產(chǎn)生的答案。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完全問題

通常認(rèn)為的P、NP、NPComplete、NPHard問題的關(guān)系：PNPNPCompleteNPHard7.8NP難與NP完全問題

通常認(rèn)為的P、NP、NPCo397.8NP難與NP完全問題

NP完全問題的特性為：當(dāng)且僅當(dāng)所有其它NP完全問題可以在多項式時間內(nèi)求解，該問題可以在多項式時間內(nèi)求解。如果一個NP難問題可以在多項式時間內(nèi)求解，則所有的NP完全問題都可以在多項式時間內(nèi)求解。NP完全和NP難問題都不是多項式時間可解的。7.8NP難與NP完全問題

NP完全問題的特性為：當(dāng)且僅當(dāng)40第七章隨機(jī)算法及NP完全問題7.1隨機(jī)算法引言7.2隨機(jī)算法的類型7.3隨機(jī)數(shù)發(fā)生器7.4數(shù)值概率算法7.5舍伍德(Sherwood)算法7.6拉斯維加斯（LasVegas）算法7.7蒙特卡羅（MonteCarlo）算法7.8NP完全問題第七章隨機(jī)算法及NP完全問題7.1隨機(jī)算法引言417.1隨機(jī)算法引言確定性的算法：算法的每一個計算步驟都是確定的，對于相同的輸出，每一次執(zhí)行過程都會產(chǎn)生相同的輸出。隨機(jī)算法：非形式描述隨機(jī)算法為使用隨機(jī)函數(shù)產(chǎn)生器的算法。算法中的一些判定依賴于隨機(jī)函數(shù)產(chǎn)生器的輸出。隨機(jī)算法對于相同的輸入，在不同的運行過程中會得到不同的輸出。對于相同的輸入，隨機(jī)算法的執(zhí)行時間也可能隨不同的運行過程而不同。7.1隨機(jī)算法引言確定性的算法：428.1隨機(jī)算法引言隨機(jī)算法的優(yōu)點：1、執(zhí)行時間和空間，小于同一問題的已知最好的確定性算法；2、實現(xiàn)比較簡單，容易理解。很多確定性的算法，其性能很壞?？捎秒S機(jī)選擇的方法來改善算法的性能。某些方面可能不正確，對特定的輸入，算法的每一次運行不一定得到相同結(jié)果。出現(xiàn)這種不正確的可能性很小，以致可以安全地不予理睬。8.1隨機(jī)算法引言隨機(jī)算法的優(yōu)點：437.2隨機(jī)算法的類型數(shù)值概率算法拉斯維加斯（LasVegas）算法蒙特卡羅（MonteCarlo）算法舍伍德（Sherwood）算法。7.2隨機(jī)算法的類型數(shù)值概率算法447.2隨機(jī)算法的類型1、數(shù)值概率算法：用于數(shù)值問題的求解。所得到的解幾乎都是近似解，近似解的精度隨著計算時間的增加而不斷地提高。2、舍伍德（Sherwood）算法：很多具有很好的平均運行時間的確定性算法，在最壞的情況下性能很壞。引入隨機(jī)性加以改造，可以消除或減少一般情況和最壞情況的差別。7.2隨機(jī)算法的類型1、數(shù)值概率算法：用于數(shù)值問題的求解。457.2隨機(jī)算法的類型3、拉斯維加斯（LasVegas）算法：要么給出問題的正確答案，要么得不到答案。反復(fù)求解多次，可使失效的概率任意小。4、蒙特卡羅（MonteCarlo）算法：總能得到問題的答案，偶然產(chǎn)生不正確的答案。重復(fù)運行，每一次都進(jìn)行隨機(jī)選擇，可使不正確答案的概率變得任意小。7.2隨機(jī)算法的類型3、拉斯維加斯（LasVegas）算467.3隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)的公式：

產(chǎn)生0~65535的隨機(jī)數(shù)序列，b、c、d為正整數(shù)，稱為所產(chǎn)生的隨機(jī)序列的種子。常數(shù)b、c，對所產(chǎn)生的隨機(jī)序列的隨機(jī)性能有很大的關(guān)系，b通常取一素數(shù)。7.3隨機(jī)數(shù)發(fā)生器產(chǎn)生隨機(jī)數(shù)的公式：477.3隨機(jī)數(shù)發(fā)生器#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隨機(jī)數(shù)發(fā)生器#define MULTIPLIER 0487.4數(shù)值概率算法例：用隨機(jī)投點法計算值設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機(jī)地投擲n個點。設(shè)落入圓內(nèi)的點數(shù)為k。由于所投入的點在正方形上均勻分布，因而所投入的點落入圓內(nèi)的概率為。所以當(dāng)n足夠大時，k與n之比就逼近這一概率。從而7.4數(shù)值概率算法例：用隨機(jī)投點法計算值497.4數(shù)值概率算法publicdoubledarts(intn){//用隨機(jī)投點法計算值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數(shù)值概率算法publicdoubledarts(507.5舍伍德(Sherwood)算法一、確定性算法的平均運行時間TA(x)：確定性算法對輸入實例的運行時間。Xn：規(guī)模為的所有輸入實例全體。算法的平均運行時間：存在實例，。例：快速排序算法當(dāng)輸入數(shù)據(jù)均勻分布時，運行時間是。當(dāng)輸入數(shù)據(jù)按遞增或遞減順序排列時，算法的運行時間變壞7.5舍伍德(Sherwood)算法一、確定性算法的平均運517.5舍伍德(Sherwood)算法二、舍伍德算法的基本思想消除不同輸入實例對算法性能的影響，使隨機(jī)算法對規(guī)模為的每一個實例，都有：三、期望運行時間：

當(dāng)s(n)與相比很小可以忽略時，舍伍德算法有很好的性能。對所有輸入實例而言，運行時間相對均勻。時間復(fù)雜性與確定性算法的時間復(fù)雜性相當(dāng).7.5舍伍德(Sherwood)算法二、舍伍德算法的基本思527.5舍伍德(Sherwood)算法隨機(jī)快速排序算法算法9.1隨機(jī)選擇樞點的快速排序算法輸入：數(shù)組A,數(shù)組元素的的起始位置low,終止位置high輸出：按非降順序排序的數(shù)組A

1.template<classType>2.voidquicksort_random(TypeA[],intlow,inthigh)3.{4.random_seed(0);/*選擇系統(tǒng)當(dāng)前時間作為隨機(jī)數(shù)種子*/5.r_quicksort(A,low,high); /*遞歸調(diào)用隨機(jī)快速排序算法*/6.}7.5舍伍德(Sherwood)算法隨機(jī)快速排序算法537.5舍伍德(Sherwood)算法1.voidr_quicksort(TypeA[],intlow,inthigh)2.{3.intk;4.if(low<high){5.k=random(low,high);/*產(chǎn)生low到high之間的隨機(jī)數(shù)k*/6.swap(A[low],A[k]);/*把元素A[k]交換到數(shù)組的第一個位置*/7.k=split(A,low,high); /*按元素A[low]把數(shù)組劃分為兩個*/8.r_quicksort(A,low,k-1); /*排序第一個子數(shù)組*/9.r_quicksort(A,k+1,high); /*排序第二個子數(shù)組*/10.}11.}算法的期望運行時間是。7.5舍伍德(Sherwood)算法1.voidr_q547.6拉斯維加斯（LasVegas）算法一、一般概念 拉斯維加斯算法有時運行成功，有時失敗，需要反復(fù)運行同一實例，直到成功為止。 BOOLlas_vegas()：解問題的某個實例的代碼段。運行成功返回true，否則返回false。 拉斯維加斯算法反復(fù)地運行下面的代碼段： while(!las_vegas(P(x))); 直到運行成功返回為止。7.6拉斯維加斯（LasVegas）算法一、一般概念557.6拉斯維加斯（LasVegas）算法p(x)：對輸入實例成功地運行l(wèi)as_vegas的概率若存在常數(shù)δ>0，使得對的所有實例p，都有p(x)>=δ，則失敗的概率小于1-δ。連續(xù)運行k次，失敗的概率降低為(1-δ)k。k充分大，(1-δ)k趨于0。7.6拉斯維加斯（LasVegas）算法p(x)：對輸入567.6拉斯維加斯（LasVegas）算法例：識別重復(fù)元素考慮一個有n個數(shù)字的數(shù)組a[]，其中有n/2個不同的元素，其余元素是另一個元素的拷貝，即數(shù)組中共有（n/2）+1個不同的元素。問題是要識別重復(fù)的元素。確定性算法： 至少需要（n/2）+2個時間步。7.6拉斯維加斯（LasVegas）算法例：識別重復(fù)元素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循環(huán)則任何一次迭代中退出的概率為p=.當(dāng)n≥10時，p≥1/5,則不退出的概率≤4/5。算法在前calogn(c為固定常數(shù))次迭代內(nèi)不退出的概率<(4/5)calogn=n-calog(4/5),若取c≥1/log(5/4),則其值<n-a,因此，算法在calogn次迭代以內(nèi)終止的概率≥1-n-a。每次迭代花費O(1)的時間，算法的執(zhí)行時間為O(logn)。7.6拉斯維加斯（LasVegas）算法while循環(huán)則597.7蒙特卡羅（MonteCarlo）算法蒙特卡羅算法則在一般情況下可以保證對問題的所有實例都以高概率給出正確解，但是通常無法判定一個具體解是否正確。設(shè)p是一個實數(shù)，且1/2<p<1。如果一個蒙特卡羅算法對于問題的任一實例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢。如果對于同一實例，蒙特卡羅算法不會給出2個不同的正確解答，則稱該蒙特卡羅算法是一致的。7.7蒙特卡羅（MonteCarlo）算法蒙特卡羅算法607.7蒙特卡羅（MonteCarlo）算法數(shù)組的主元素問題一、問題n個元素的數(shù)組A，A中元素x，若A中一半以上元素與x相同，稱x是A的主元素。例：序列1,3,2,3,3,4,3中，元素3是主元素。二、一般方法每個元素和其它元素比較，并計數(shù)。如果計數(shù)值大于n/2，該元素就是的主元素。元素比較次數(shù)為。7.7蒙特卡羅（MonteCarlo）算法數(shù)組的主元素問617.7蒙特卡羅（MonteCarlo）算法三、蒙特卡羅算法1、隨機(jī)選擇元素A[i]進(jìn)行測試，若返回true，A[i]就是主元素；否則不是主元素。7.7蒙特卡羅（MonteCarlo）算法三、蒙特卡羅算627.7蒙特卡羅（MonteCarlo）算法算法9.7求數(shù)組A的主元素輸入：n個元素的數(shù)組A[]輸出：數(shù)組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。連續(xù)運行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;}算法的錯誤概率小于所給參數(shù)e。算法的運行時間為O(nlog(1/e))。7.7蒙特卡羅（MonteCarlo）算法BOOLma657.7蒙特卡羅（MonteCarlo）算法素數(shù)測試一、一般方法被測試的數(shù)除以2到的數(shù)，余數(shù)為0，是合數(shù)，否則是素數(shù)。二、蒙特卡羅算法7.7蒙特卡羅（MonteCarlo）算法素數(shù)測試66素數(shù)測試Wilson定理：對于給定的正整數(shù)n，判定n是一個素數(shù)的充要條件是(n-1)!-1(modn)。費爾馬小定理：如果p是一個素數(shù)，且0<a<p，則ap-1(modp)。二次探測定理：如果p是一個素數(shù)，且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是奇數(shù)result=(result*a)%n;}returnresult;}booleanprime(intn){//素數(shù)測試的蒙特卡羅算法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正確的蒙特卡羅算法。通過多次重復(fù)調(diào)用錯誤概率不超過(1/4)k。這是一個很保守的估計，實際使用的效果要好得多。素數(shù)測試Wilson定理：對于給定的正整數(shù)n，判定n是一個素677.8NP難與NP完全問題一、易解的問題和難解的問題存在多項式時間算法的問題，稱為易解的問題指數(shù)時間算法或排列時間算法的問題，稱為難解的問題二、難解問題的計算相關(guān)性計算相關(guān)：某類問題可以歸約為另一類問題計算相關(guān)的問題，若它們之一可用多項式時間求解，則其它同類問題也可用多項式時間求解；若它們之一肯定不存在多項式時間算法，則同類的其它問題，也肯定不會找到多項式時間算法。7.8NP難與NP完全問題一、易解的問題和難解的問題687.8NP難與NP完全問題

P類和NP類問題定義12.1是問題的一個算法。如果在處理問題的實例時，在算法的整個執(zhí)行過程中，每一步只有一個確定的選擇，就說算法是