第12章概率算法

1、第第1212章章 概率算法概率算法n學(xué)習(xí)要點(diǎn)學(xué)習(xí)要點(diǎn): : 理解產(chǎn)生偽隨機(jī)數(shù)的算法理解產(chǎn)生偽隨機(jī)數(shù)的算法掌握舍伍德算法的設(shè)計(jì)思想掌握舍伍德算法的設(shè)計(jì)思想掌握拉斯維加斯算法的設(shè)計(jì)思想掌握拉斯維加斯算法的設(shè)計(jì)思想掌握蒙特卡羅算法的設(shè)計(jì)思想掌握蒙特卡羅算法的設(shè)計(jì)思想12.1.1 概率算法設(shè)計(jì)思想概率算法設(shè)計(jì)思想n在多數(shù)情況下，當(dāng)算法在執(zhí)行過(guò)程中面臨一個(gè)選在多數(shù)情況下，當(dāng)算法在執(zhí)行過(guò)程中面臨一個(gè)選擇時(shí)，擇時(shí)，隨機(jī)性選擇常比最優(yōu)選擇省時(shí)隨機(jī)性選擇常比最優(yōu)選擇省時(shí)。因此，概。因此，概率算法可在很大程度上降低算法復(fù)雜性。率算法可在很大程度上降低算法復(fù)雜性。n概率算法放寬了概率算法放寬了“對(duì)于所有合理的輸入都

2、必須給對(duì)于所有合理的輸入都必須給出正確的輸出出正確的輸出”這一求解問題的條件，把這一求解問題的條件，把隨機(jī)性隨機(jī)性的選擇注入到算法中的選擇注入到算法中。在算法執(zhí)行某些步驟時(shí)，可以隨機(jī)地選擇下一步在算法執(zhí)行某些步驟時(shí)，可以隨機(jī)地選擇下一步該如何進(jìn)行，同時(shí)該如何進(jìn)行，同時(shí)允許結(jié)果以允許結(jié)果以較小的概率較小的概率出現(xiàn)錯(cuò)出現(xiàn)錯(cuò)誤誤，并以此為代價(jià)，獲得算法運(yùn)行時(shí)間的大幅度，并以此為代價(jià)，獲得算法運(yùn)行時(shí)間的大幅度減少。減少。12.1 概述概述n概率算法概率算法基本特征基本特征：概率算法的概率算法的輸入輸入：n原問題的輸入原問題的輸入n供算法進(jìn)行隨機(jī)選擇的供算法進(jìn)行隨機(jī)選擇的隨機(jī)數(shù)序列隨機(jī)數(shù)序列運(yùn)行過(guò)程運(yùn)行

3、過(guò)程中：中：n一處或若干處一處或若干處隨機(jī)選擇隨機(jī)選擇，根據(jù)隨機(jī)值來(lái)決定算法的運(yùn)行，根據(jù)隨機(jī)值來(lái)決定算法的運(yùn)行結(jié)果結(jié)果：n不能保證一定是正確的不能保證一定是正確的n可以限定其出錯(cuò)概率可以限定其出錯(cuò)概率不同的運(yùn)行不同的運(yùn)行中，對(duì)于相同的輸入實(shí)例可以有不同的結(jié)果。中，對(duì)于相同的輸入實(shí)例可以有不同的結(jié)果。n因此，對(duì)于相同的輸入實(shí)例，概率算法的因此，對(duì)于相同的輸入實(shí)例，概率算法的執(zhí)行時(shí)間可能不同執(zhí)行時(shí)間可能不同。n概率算法的時(shí)間復(fù)雜性：概率算法的時(shí)間復(fù)雜性： 期望期望時(shí)間復(fù)雜性時(shí)間復(fù)雜性由概率算法反復(fù)運(yùn)行同一輸入實(shí)例由概率算法反復(fù)運(yùn)行同一輸入實(shí)例所得的平均運(yùn)行時(shí)間。所得的平均運(yùn)行時(shí)間。12.1.2 隨

4、機(jī)數(shù)隨機(jī)數(shù)n隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。隨機(jī)數(shù)在概率算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上在現(xiàn)實(shí)計(jì)算機(jī)上無(wú)法產(chǎn)生真正的無(wú)法產(chǎn)生真正的隨機(jī)數(shù)，因此在隨機(jī)數(shù)，因此在概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，概率算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即即偽隨機(jī)數(shù)偽隨機(jī)數(shù)。n線性同余法線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機(jī)序列線性同余法產(chǎn)生的隨機(jī)序列a0, a1, , an滿足：滿足：其中，其中，b0，c0，m0，dm。d稱為隨機(jī)數(shù)發(fā)生稱為隨機(jī)數(shù)發(fā)生器的器的隨機(jī)種子隨機(jī)種子(Random Seed)，當(dāng)，當(dāng)b、c和和m

5、的值確的值確定后，給定一個(gè)隨機(jī)種子，由上式產(chǎn)生的隨機(jī)數(shù)定后，給定一個(gè)隨機(jī)種子，由上式產(chǎn)生的隨機(jī)數(shù)序列也就確定了。序列也就確定了。, 2 , 1mod)(10nmcbaadann從直觀上看，從直觀上看，m m應(yīng)取的充分大，因此可取應(yīng)取的充分大，因此可取m m為機(jī)器大數(shù)為機(jī)器大數(shù)；另外應(yīng)取另外應(yīng)取gcd(m,b)=1gcd(m,b)=1，因此可取，因此可取b b為一素?cái)?shù)為一素?cái)?shù)。n偽隨機(jī)數(shù)產(chǎn)生：偽隨機(jī)數(shù)產(chǎn)生：Random(n)-產(chǎn)生產(chǎn)生0 n-1范圍內(nèi)的范圍內(nèi)的隨機(jī)整數(shù)隨機(jī)整數(shù)LRandom(L, r)-產(chǎn)生產(chǎn)生Lr范圍內(nèi)的范圍內(nèi)的隨機(jī)整數(shù)隨機(jī)整數(shù)n概率算法是一般算法隨機(jī)化后的結(jié)果，它沒有擴(kuò)概率算

6、法是一般算法隨機(jī)化后的結(jié)果，它沒有擴(kuò)大原有的可計(jì)算函數(shù)的范圍，所以不會(huì)影響已有大原有的可計(jì)算函數(shù)的范圍，所以不會(huì)影響已有的可計(jì)算性概念和結(jié)果。的可計(jì)算性概念和結(jié)果。n設(shè)計(jì)概率算法的設(shè)計(jì)概率算法的步驟步驟如下如下:對(duì)給定問題設(shè)計(jì)一個(gè)確定算法對(duì)給定問題設(shè)計(jì)一個(gè)確定算法A；分析算法分析算法A的各個(gè)步驟及每一步驟的有關(guān)操作，以的各個(gè)步驟及每一步驟的有關(guān)操作，以選定選定隨機(jī)化的入口隨機(jī)化的入口和和隨機(jī)化方式隨機(jī)化方式，從而將算法，從而將算法A隨隨機(jī)化，得到概率算法機(jī)化，得到概率算法A；論證論證A是一個(gè)好的算法，即證明：是一個(gè)好的算法，即證明：A的正確性和的正確性和A比比A更好。更好。12.2.1 特點(diǎn)特

7、點(diǎn)nSherwood算法算法總能求得總能求得問題的問題的一個(gè)正確解一個(gè)正確解；nSherwood算法算法能消除能消除算法算法最壞特性最壞特性與與平均特性平均特性之之間的差別。間的差別。設(shè)：一個(gè)確定型算法設(shè)：一個(gè)確定型算法A，它求解問題規(guī)模為，它求解問題規(guī)模為n的所有的所有輸入實(shí)例的平均時(shí)間是輸入實(shí)例的平均時(shí)間是TA(n)。而一個(gè)而一個(gè)Sherwood型隨機(jī)算法型隨機(jī)算法B，它求解問題規(guī)模為，它求解問題規(guī)模為n的輸入實(shí)例的時(shí)間是的輸入實(shí)例的時(shí)間是TB(n)。一般地，有：一般地，有：TB(n) = TA(n) + s(n) Sherwood型隨機(jī)算法型隨機(jī)算法B本身的隨機(jī)特性本身的隨機(jī)特性12.2

8、 舍伍德舍伍德(Sherwood)型概率算法型概率算法 對(duì)于問題的某一輸入實(shí)例，有：對(duì)于問題的某一輸入實(shí)例，有：TB(n) TA(n)但，其原因是但，其原因是隨機(jī)算法本身的隨機(jī)性隨機(jī)算法本身的隨機(jī)性，而不在于問，而不在于問題的實(shí)例！題的實(shí)例！設(shè)：設(shè)：Sherwood型隨機(jī)算法型隨機(jī)算法B的平均時(shí)間是的平均時(shí)間是TB(n)。則有：則有：TB(n) = TA(n) + s(n) 其中，其中，s(n)TA(n) 舍伍德型概率算法舍伍德型概率算法不是避免不是避免算法的最壞情況行為，算法的最壞情況行為，而是而是設(shè)設(shè)法法消除消除算法的不同輸入實(shí)例對(duì)算法時(shí)間性能的影響。算法的不同輸入實(shí)例對(duì)算法時(shí)間性能的影響

9、。 對(duì)所有輸入實(shí)例而言，舍伍德型概率算法的運(yùn)行時(shí)間相對(duì)對(duì)所有輸入實(shí)例而言，舍伍德型概率算法的運(yùn)行時(shí)間相對(duì)比較均勻。比較均勻。12.2.2 舍伍德型概率算法舉例舍伍德型概率算法舉例n快速排序的概率算法快速排序的概率算法例例12-1:快速排序?？焖倥判?。關(guān)鍵在于一次劃分中選擇合適的軸值作為劃分的關(guān)鍵在于一次劃分中選擇合適的軸值作為劃分的基準(zhǔn)?；鶞?zhǔn)。n當(dāng)輸入數(shù)據(jù)是當(dāng)輸入數(shù)據(jù)是均勻分布均勻分布時(shí)，快速排序算法所需的平時(shí)，快速排序算法所需的平均時(shí)間是均時(shí)間是O(nlog2n)； n輸入輸入已經(jīng)基本排好序已經(jīng)基本排好序時(shí)，所用時(shí)間就大大增加了，時(shí)，所用時(shí)間就大大增加了，最壞是最壞是O(n2) 。采用舍伍德

10、算法采用舍伍德算法消除消除算法所需算法所需計(jì)算時(shí)間計(jì)算時(shí)間與與輸入實(shí)輸入實(shí)例例間的這種聯(lián)系。間的這種聯(lián)系。 快速排序的舍伍德型算法思想：快速排序的舍伍德型算法思想：一次劃分結(jié)果一次劃分結(jié)果 6 13 192331 35 58(調(diào)用調(diào)用Partition)初始鍵值序列初始鍵值序列 6 13 19 23 31 35 58一次劃分結(jié)果一次劃分結(jié)果 613 19 23 31 35 58(調(diào)用調(diào)用Partition)初始鍵值序列初始鍵值序列 6 13 19 23 31 35 58隨機(jī)選擇一個(gè)隨機(jī)選擇一個(gè) 23 13 19 6 31 35 58記錄與記錄與6交換交換(a) 以最小值以最小值6為軸值，劃分不

11、均衡為軸值，劃分不均衡(b) 隨機(jī)選擇軸值，劃分均衡隨機(jī)選擇軸值，劃分均衡6jiji算法描述：算法描述：void R_QuickSort (int r , int low, int high) if (lows，則，則rk在軸值的后面在軸值的后面)(ks，則，則rk在軸值的前面在軸值的前面)(k=s，則，則rk=rs)K-選擇的舍伍德型算法思想：選擇的舍伍德型算法思想： 在一次劃分之前，根據(jù)隨機(jī)數(shù)在待劃分序列中隨機(jī)確在一次劃分之前，根據(jù)隨機(jī)數(shù)在待劃分序列中隨機(jī)確定一個(gè)記錄作為軸值，并把它與第一個(gè)記錄交換，則定一個(gè)記錄作為軸值，并把它與第一個(gè)記錄交換，則一次劃分后得到期望均衡的兩個(gè)子序列，使得選

12、擇問一次劃分后得到期望均衡的兩個(gè)子序列，使得選擇問題在最壞情況下的時(shí)間性能趨近于平均情況的時(shí)間性題在最壞情況下的時(shí)間性能趨近于平均情況的時(shí)間性能。能。int R_K-Select(int r , int low, int high, int k) if (high-lows) return R_K-Select(r, low, s-1, k); /在前半部分繼續(xù)查找在前半部分繼續(xù)查找 else return R_K-Select(r, s+1, high, k); /在后半部分繼續(xù)查找在后半部分繼續(xù)查找 n隨機(jī)預(yù)處理技術(shù)隨機(jī)預(yù)處理技術(shù)不改變不改變?cè)械拇_定性算法，僅對(duì)其輸入進(jìn)行隨機(jī)原有的確定性

13、算法，僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，同樣可以得到舍伍德算法的效果。洗牌，同樣可以得到舍伍德算法的效果。假設(shè)輸入實(shí)例為整型，下面的隨機(jī)洗牌算法可在假設(shè)輸入實(shí)例為整型，下面的隨機(jī)洗牌算法可在線性時(shí)間實(shí)現(xiàn)對(duì)輸入實(shí)例的隨機(jī)排列。線性時(shí)間實(shí)現(xiàn)對(duì)輸入實(shí)例的隨機(jī)排列。void RandomShuffle(int n, int r ) for (i=0; i0。n設(shè)設(shè)t(x)是算法是算法Obstinate找到具體實(shí)例找到具體實(shí)例x的一個(gè)解所的一個(gè)解所需的平均時(shí)間，需的平均時(shí)間，s(x)和和e(x)分別是算法對(duì)于具體實(shí)分別是算法對(duì)于具體實(shí)例例x求解求解成功成功或求解或求解失敗失敗所需的平均時(shí)間，則有：所需的平均時(shí)間，

14、則有： 解此方程可得：解此方程可得：n能顯著能顯著改進(jìn)改進(jìn)算法的算法的時(shí)間復(fù)雜性時(shí)間復(fù)雜性！)()()(1 ()()()(xtxexpxsxpxt)()()(1)()(xexpxpxsxt12.3.3 拉斯維加斯型概率算法舉例拉斯維加斯型概率算法舉例nn-皇后問題?；屎髥栴}。例例12-3:問題描述問題描述(略略)。分析分析(略略)拉斯維加斯算法思想：拉斯維加斯算法思想： 在棋盤上在棋盤上相繼的各行中隨機(jī)地放置相繼的各行中隨機(jī)地放置皇后，并注意皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至使新放置的皇后與已放置的皇后互不攻擊，直至n個(gè)個(gè)皇后均已相容地放置好，或已沒有下一個(gè)皇后的可皇后均已

15、相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。放置位置時(shí)為止。算法描述：算法描述：Qbool LV_Queens( int n ) 初始化：初始化：c, a, d; / c：“監(jiān)視監(jiān)視”列方向；列方向； / a：“監(jiān)視監(jiān)視”反對(duì)角線方向；反對(duì)角線方向； / d：“監(jiān)視監(jiān)視”對(duì)角線方向。對(duì)角線方向。 int k = 1; int count = 1; int i, j; while ( (count 0) & (k = n) ) count = 0; j = 0; for ( i = 1; i 0 ) /第第k行找到一個(gè)行找到一個(gè)“合適合適”位置！位置！ xk = j; 設(shè)置設(shè)置c, a,

16、 d標(biāo)志；標(biāo)志； k +; Q1c:x:a:d:FFF1234 if (count = 0) /第第k行沒有找到行沒有找到“合適合適”位置！位置！ return(false); else return(true); /成功地設(shè)置了成功地設(shè)置了n個(gè)個(gè)“皇后皇后”！void nQueen(int n) 初始化：初始化：X; /X:解向量。解向量。 bool success = false; int sum = 0； while ( ( ! success) & (sum 20) success = LV_Queens(n) ; sum+; /反復(fù)調(diào)用反復(fù)調(diào)用LV_Queens，直到得，直到得到到n

17、皇后問題的一個(gè)解?；屎髥栴}的一個(gè)解。 if (success) 輸出輸出X;如果將上述隨機(jī)放置策略如果將上述隨機(jī)放置策略與回溯法相結(jié)合與回溯法相結(jié)合，則會(huì)，則會(huì)獲得更好的效果。獲得更好的效果。n先在棋盤的若干行中隨機(jī)地放置相容的皇后；先在棋盤的若干行中隨機(jī)地放置相容的皇后；n然后在其他行中用回溯法繼續(xù)放置，直至找到一個(gè)解或然后在其他行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。宣告失敗。n“整數(shù)因子整數(shù)因子”分解問題。分解問題。例例12-4:設(shè)設(shè)n是正整數(shù)且是正整數(shù)且n1，整數(shù)，整數(shù)n的因子分解問題的因子分解問題是找出是找出n的如下形式的惟一分解式：的如下形式的惟一分解式： 其中，其中，p1

18、p2pk是是素?cái)?shù)素?cái)?shù)，m1, m2, , mk是是正正整數(shù)整數(shù)。如果。如果n是一個(gè)合數(shù)，則是一個(gè)合數(shù)，則n必有一個(gè)必有一個(gè)非平凡因非平凡因子子m(1mn)，使得，使得m可以整除可以整除n。給定一個(gè)合數(shù)。給定一個(gè)合數(shù)n，求，求n的一個(gè)非平凡因子的問題稱為的一個(gè)非平凡因子的問題稱為整數(shù)因子劃整數(shù)因子劃分問題分問題。對(duì)一個(gè)正整數(shù)對(duì)一個(gè)正整數(shù)n進(jìn)行因子劃分的進(jìn)行因子劃分的最自然的想法是試最自然的想法是試除除，它可以找到，它可以找到n的最小素?cái)?shù)因子。算法如下：的最小素?cái)?shù)因子。算法如下：kmkmmpppn2121int factor( int n ) int i, m; m = sqrt( (double

19、)n ); for ( i=2; im; i+ ) /對(duì)范圍在對(duì)范圍在1 的所有整數(shù)進(jìn)行試除的所有整數(shù)進(jìn)行試除 if ( n % i = 0 ) return(i); return(1);算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度O(n1/2)求解整數(shù)因子劃分問題的求解整數(shù)因子劃分問題的拉斯維加斯型概率算法拉斯維加斯型概率算法：n選取選取1n或或0n-1范圍內(nèi)的范圍內(nèi)的隨機(jī)數(shù)隨機(jī)數(shù)x1，n然后遞歸地由下式然后遞歸地由下式產(chǎn)生無(wú)窮序列產(chǎn)生無(wú)窮序列x1, x2, , xk, 。nxxiimod)1(21nn對(duì)于對(duì)于i=2k(k=0, 1, 2, )，以及，以及2kj2k+1，計(jì)算計(jì)算xj-xi與與n的最大公因子

20、的最大公因子d。如果如果d大于大于1，則，則d即是即是n的非平凡的非平凡因子，算法實(shí)現(xiàn)對(duì)因子，算法實(shí)現(xiàn)對(duì)n的一次劃分。算法如下：的一次劃分。算法如下：int Pollard( int n ) int i, k, x, y, d = 0; i = 1; k = 2; x = LRandom(1, n); y = x; while ( i 1) & (dn) ) break; /d是是n的非平凡因子的非平凡因子 else if ( i=k ) y = x; k *= 2; return(d); 令令:x1= LRandom(1, n), 且有且有: xi = (x2i-1 1) mod n,則，則

21、，Pollard算法的算法的while循環(huán)依次計(jì)算如下兩個(gè)整循環(huán)依次計(jì)算如下兩個(gè)整數(shù)的最大公因子：數(shù)的最大公因子： k=2(i=1, j=2): (n, x2-x1) k=4(i=2, j=3,4): (n, x3-x2)，(n, x4-x2) k=8(i=4, j=5,6,7,8): (n, x5-x4)，(n, x6-x4) (n, x7-x4)，(n, x8-x4) k=16：（：（n, x8-x9），（），（n, x8-x10） . 若若n存在因子存在因子d，則，則while循環(huán)將執(zhí)行循環(huán)將執(zhí)行d1/2次。次。而而n的最小的最小dn1/2， 算法時(shí)間復(fù)雜度算法時(shí)間復(fù)雜度O(n1/4)1

22、2.4 蒙特卡羅蒙特卡羅(Monte Carlo)型概率算法型概率算法12.4.1 特點(diǎn)特點(diǎn)nMonte Carlo算法算法總能求得總能求得問題實(shí)例的問題實(shí)例的解解；nMonte Carlo算法算法可能可能返回返回不正確的解不正確的解。算法求得正確解的概率依賴于算法所用的時(shí)間，算法求得正確解的概率依賴于算法所用的時(shí)間，算法所用時(shí)間越多，得到正確解的概率就越高。算法所用時(shí)間越多，得到正確解的概率就越高。n算法的參數(shù)：算法的參數(shù)：描述問題實(shí)例的輸入?yún)?shù)描述問題實(shí)例的輸入?yún)?shù)I；描述錯(cuò)誤解可接受概率的參數(shù)描述錯(cuò)誤解可接受概率的參數(shù)。n用于用于求求問題的問題的準(zhǔn)確解準(zhǔn)確解。12.4.2 蒙特卡羅型概率

23、算法舉例蒙特卡羅型概率算法舉例n主元素問題。主元素問題。例例12-5:設(shè)設(shè)T1Tn是一個(gè)含有是一個(gè)含有n個(gè)元素的數(shù)組。當(dāng)個(gè)元素的數(shù)組。當(dāng)T中取值等于中取值等于x的元素個(gè)數(shù)大于的元素個(gè)數(shù)大于n/2時(shí)，稱時(shí)，稱x是是T的的主元素主元素。試設(shè)計(jì)算法找出。試設(shè)計(jì)算法找出T的主元素。的主元素。蒙特卡羅型蒙特卡羅型概率算法概率算法求解思想求解思想：隨機(jī)地選擇數(shù)組隨機(jī)地選擇數(shù)組中的一個(gè)元素中的一個(gè)元素Ti進(jìn)行統(tǒng)計(jì)，如果該元素出現(xiàn)的次進(jìn)行統(tǒng)計(jì)，如果該元素出現(xiàn)的次數(shù)大于數(shù)大于n/2，則該元素就是數(shù)組的主元素，算法返，則該元素就是數(shù)組的主元素，算法返回回true；否則隨機(jī)選擇的這個(gè)元素；否則隨機(jī)選擇的這個(gè)元素Ti

24、不是主元素，不是主元素，算法返回算法返回false。算法如下：。算法如下：bool MC_Majority( Type A, int n, Type &x ) int i, j, sum; i = Random(n); x = Ai; sum = 0; for ( j = 0; j n / 2 ) return(true); else return(false);如，如， 數(shù)組數(shù)組T7=3, 2, 3, 2, 3, 3, 5。當(dāng)當(dāng)i= Random(7)=0、2.時(shí)，算法返回正確的結(jié)果；時(shí)，算法返回正確的結(jié)果；當(dāng)當(dāng)i= Random(7)=1、3等時(shí)，算法返回錯(cuò)誤的結(jié)果。等時(shí)，算法返回錯(cuò)誤的結(jié)

25、果。算法的輸出結(jié)論符合算法的輸出結(jié)論符合問題實(shí)例的實(shí)際情況嗎？問題實(shí)例的實(shí)際情況嗎？“主元素問題主元素問題” Monte Carlo算法的分析：算法的分析： 根據(jù)算法思想，算法返回根據(jù)算法思想，算法返回True的概率的概率1/2，而返，而返回回false的概率的概率1/2。 算法返回錯(cuò)誤結(jié)論的概率算法返回錯(cuò)誤結(jié)論的概率1/2 若執(zhí)行若執(zhí)行MC_Majority算法算法k次，則算法返回錯(cuò)誤次，則算法返回錯(cuò)誤結(jié)論的概率結(jié)論的概率2-k。令：算法返回錯(cuò)誤結(jié)論的概率為令：算法返回錯(cuò)誤結(jié)論的概率為， 由由2-k = ，有：，有：k = log(1/)。即，在即，在重復(fù)執(zhí)行重復(fù)執(zhí)行k次次Monte Car

26、lo算法中，算法中，只要有一次只要有一次返回返回true，就可以判斷存在主元素，且算法返回錯(cuò)，就可以判斷存在主元素，且算法返回錯(cuò)誤結(jié)論的概率小于誤結(jié)論的概率小于。改進(jìn)改進(jìn)“主元素問題主元素問題”的的Monte Carlo算法：算法：bool MC_Majority_2( int n, Type &x, double ) int i, j, k, m, sum; bool flag = false; k = log(1 /); for ( m = 1; m = k; m+ ) i = Random(n); x = Ai; sum = 0; for ( j = 0; j n / 2 ) flag

27、= true; break; return(flag);算法時(shí)間復(fù)雜度：算法時(shí)間復(fù)雜度：O(nlog(1/)12.4.3 蒙特卡羅型概率算法的正確性蒙特卡羅型概率算法的正確性設(shè)：設(shè)：MC(x)是求解問題實(shí)例是求解問題實(shí)例x的的Monte Carlo算法。算法。n定義：定義： MC(x)算法是算法是p正確的正確的。 設(shè)：設(shè)：p是一個(gè)實(shí)數(shù)，且是一個(gè)實(shí)數(shù)，且1/2 p 1。如果。如果MC(x)算法對(duì)于問題的任意一個(gè)實(shí)例得到正確解的概率算法對(duì)于問題的任意一個(gè)實(shí)例得到正確解的概率不小于不小于p，則稱該，則稱該MC(x)算法是算法是p正確的。正確的。n定義：定義： MC(x)算法是算法是一致的一致的。 如

28、果如果MC(x)算法對(duì)于問題的同一個(gè)實(shí)例算法對(duì)于問題的同一個(gè)實(shí)例x不會(huì)給不會(huì)給出兩個(gè)不同的正確答案，則稱該出兩個(gè)不同的正確答案，則稱該MC(x)算法是一算法是一致的。致的。n定義：定義：MC(x)算法是算法是偏偏y0的的 對(duì)于一個(gè)求解問題的算法對(duì)于一個(gè)求解問題的算法MC(x)，如果存在問，如果存在問題實(shí)例的子集題實(shí)例的子集X，使得：，使得：當(dāng)當(dāng)x X 時(shí)，時(shí)，MC(x)返回的解是正確的；返回的解是正確的；當(dāng)當(dāng)x X時(shí)，正確解是時(shí)，正確解是y0，但，但MC(x)返回的解不一返回的解不一定是定是y0。 則稱算法則稱算法MC(x)是偏是偏y0的。的。n兩個(gè)結(jié)論：兩個(gè)結(jié)論：結(jié)論一結(jié)論一：如果重復(fù)運(yùn)行一個(gè)：如果重復(fù)運(yùn)行一個(gè)一致的一致的、p正確的正確的Monte Carlo算法（每次運(yùn)行獨(dú)立地進(jìn)行隨機(jī)選算法（每次運(yùn)行獨(dú)立地進(jìn)行隨機(jī)選擇！），則可以使產(chǎn)生不正確答案的概率變得很擇?。瑒t可以使產(chǎn)生不正確答案的概率變得很小。小。結(jié)論二結(jié)論二：重復(fù)調(diào)用一個(gè)一致的、：重復(fù)調(diào)用一個(gè)一致的、p正確、偏正確、偏y0的的Monte Ca