1、1,第7章 隨機(jī)算法,2,學(xué)習(xí)要點(diǎn) 了解隨機(jī)算法的基本特征 理解產(chǎn)生偽隨機(jī)數(shù)的算法 掌握數(shù)值隨機(jī)化算法的設(shè)計(jì)思想 掌握舍伍德算法的設(shè)計(jì)思想 掌握拉斯維加斯算法的設(shè)計(jì)思想 掌握蒙特卡羅算法的設(shè)計(jì)思想,3,概述,前面各章討論的算法的每一個(gè)步驟都是確定的，而本章討論的隨機(jī)算法允許算法在執(zhí)行過程中隨機(jī)地選擇一下計(jì)算步驟。,在許多情況下，一般算法比較復(fù)雜，性能較差，很多具有很好平均運(yùn)行時(shí)間的算法，在最壞的情況下，卻具有很壞的性能。由于隨機(jī)性選擇比最優(yōu)選擇省時(shí)間，因此引入隨機(jī)化算法可以在很大程度上降低算法的復(fù)雜度。,4,很早以前就被人們所發(fā)現(xiàn)和利用。17世紀(jì)，人們就知道用事件發(fā)生的“頻率”來決定事件的“概

2、率”。19世紀(jì)人們用投針試驗(yàn)的方法來決定。高速計(jì)算機(jī)的出現(xiàn)，使得用數(shù)學(xué)方法在計(jì)算機(jī)上大量模擬這樣的試驗(yàn)成為可能。,5,從Buffon(蒲豐)投針問題談起,6,7,8,概述,隨機(jī)算法對(duì)所求解問題的同一個(gè)實(shí)例用同一隨機(jī)算法求解兩次可能得到完全不同的效果。這兩次求解所需要的時(shí)間，甚至所得到的結(jié)果都可能會(huì)有相當(dāng)大的差別。 包括 數(shù)值概率算法 蒙特卡羅（Monte Carlo）算法 拉斯維加斯（Las Vegas）算法 舍伍德（Sherwood）算法,9,數(shù)值概率算法常用于數(shù)值問題的求解。將一個(gè)問題的計(jì)算與某個(gè)概率分布已經(jīng)確定的事件聯(lián)系起來，求問題的近似解。這類算法所得到的往往是近似解，且近似解的精度隨

3、計(jì)算時(shí)間的增加而不斷提高。在許多情況下，要計(jì)算出問題的精確解是不可能或沒有必要的，因此可以用數(shù)值隨機(jī)化算法得到相當(dāng)滿意的解。,蒙特卡羅算法用于求問題的準(zhǔn)確解，但得到的解未必是正確的。蒙特卡羅算法以正的概率給出正解，求得正確解的概率依賴于算法所用的時(shí)間。算法所用的時(shí)間越多，得到正確解的概率就越高。一般給定執(zhí)行步驟的上界，給定一個(gè)輸入，算法都是在一個(gè)固定的步數(shù)內(nèi)停止的。,隨機(jī)算法的分類,10,舍伍德算法總能求得問題的一個(gè)解，且所求得的解總是正確的。當(dāng)一個(gè)確定性算法在最壞情況下的計(jì)算復(fù)雜性與其在平均情況下的計(jì)算復(fù)雜性有較大差別時(shí)，可在這個(gè)確定性算法中引入隨機(jī)性將它改造成一個(gè)舍伍德算法，消除或減少問題

4、的好壞實(shí)例間的這種差別（精髓所在）。,拉斯維加斯算法不會(huì)得到不正確的解。一旦用拉斯維加斯算法找到一個(gè)解，這個(gè)解就一定是正確解。但有時(shí)可能找不到解。拉斯維加斯算法找到正確解的概率隨著它所用的計(jì)算時(shí)間的增加而提高。對(duì)于所求解問題的任意實(shí)例，用同一拉斯維加斯算法反復(fù)對(duì)它求解，可以使求解失效的概率任意小。,隨機(jī)算法的分類,11,7.1隨機(jī)數(shù),12,7.1隨機(jī)數(shù),隨機(jī)數(shù)在隨機(jī)化算法設(shè)計(jì)中扮演著十分重要的角色。在現(xiàn)實(shí)計(jì)算機(jī)上無法產(chǎn)生真正的隨機(jī)數(shù)，因此在隨機(jī)化算法中使用的隨機(jī)數(shù)都是一定程度上隨機(jī)的，即偽隨機(jī)數(shù)。 線性同余法是產(chǎn)生偽隨機(jī)數(shù)的最常用的方法。由線性同余法產(chǎn)生的隨機(jī)序列a0,a1,an，滿足：(混合

5、同余法) 其中b0，c0，dm。d稱為該隨機(jī)序列的種子。如何選取該方法中的常數(shù)b、c和m直接關(guān)系到所產(chǎn)生的隨機(jī)序列的隨機(jī)性能。這是隨機(jī)性理論研究的內(nèi)容，已超出本書討論的范圍。從直觀上看，m應(yīng)取得充分大，因此可取m為機(jī)器大數(shù)。,13,d = 1 種子 m= 11 b=6 c = 0 (1,6,3,7,9,10,5,8,4,2,1,6,3),14,復(fù)雜一些的生成器,Multiple recursive generator,15,算法實(shí)現(xiàn),許多程序語言中都自帶生成隨機(jī)數(shù)的方法，如 c 中的 random() 函數(shù)，Matlab中的rand()函數(shù)等。 但這些生成器生成的隨機(jī)數(shù)效果很不一樣，比如 c

6、中的函數(shù)生成的隨機(jī)數(shù)性質(zhì)就比較差，如果用 c ，最好自己再編一個(gè)程序。Matlab 中的 rand() 函數(shù)，經(jīng)過了很多優(yōu)化?？梢援a(chǎn)生性質(zhì)很好的隨 機(jī)數(shù)，可以直接利用。,16,下面用計(jì)算機(jī)產(chǎn)生的偽隨機(jī)數(shù)來模擬拋硬幣實(shí)驗(yàn)。假設(shè)拋10次硬幣構(gòu)成一個(gè)事件。調(diào)用Random(2)返回一個(gè)二值結(jié)果。返回0表示拋硬幣得到反面，返回1表示得到正面。下面的算法TossCoins模擬拋10次硬幣這一事件50000次。用headi (0 i 10)記錄這50000此模擬恰好得到i次正面的次數(shù)。最終輸出模擬拋硬幣事件得到正面事件的頻率圖，如下圖所示：,17,0 * 1 * 2 * 3 * 4 * 5 * 6 * 7

7、 * 8 * 9 * 10 *,模擬拋硬幣得到的正面事件頻率圖,18,void main (void) / 模擬隨機(jī)拋硬幣事件 const int NCOINS = 10; const long NTOSSES = 50000L; / headsi是得到i次正面的次數(shù) long i, headsNCOINS+1; int j, position; / 初始化數(shù)組heads for (j=0;j NCOIN+1; j+) headsj = 0; / 重復(fù)50000次模擬事件 for (i=0;i NTOSSES; i+) headsTossCoins(NCOINS)+; / 輸出頻率圖 for

8、(i=0;i=NCOINS; i+) position = int (float (headsi)/NTOSSES*72); coutsetw(6)i ; for (j=0;jposition-1;j+) cout ; cout*endl; ,int TossCoins (int numberCoins) /隨機(jī)拋硬幣 static RandomNumber coinToss; int i, tosses = 0; for (i = 0; i numberCoins; i+) / Random (2) = 1 表示正面 tosses += coinToss.Random (2); return

9、 tosses; ,int TossCoins (int numberCoins) /隨機(jī)拋硬幣 static RandomNumber coinToss; int i, tosses = 0; for (i = 0; i numberCoins; i+) / Random (2) = 1 表示正面 tosses += coinToss.Random (2); return tosses; ,19,7.2 數(shù)值隨機(jī)化算法,20,7.2 數(shù)值隨機(jī)化算法,7.2.1 用隨機(jī)投點(diǎn)法計(jì)算值 設(shè)有一半徑為r的圓及其外切四邊形。向該正方形隨機(jī)地投擲n個(gè)點(diǎn)。設(shè)落入圓內(nèi)的點(diǎn)數(shù)為k。由于所投入的點(diǎn)在正方形上均勻

10、分布，因而所投入的點(diǎn)落入圓內(nèi)的概率為 。,所以當(dāng)n足夠大時(shí)，k與n之比就逼近這一概率。從而 。,21,在具體實(shí)現(xiàn)時(shí)，只要在第一象限計(jì)算即可： double Darts (int n) / 用隨機(jī)投點(diǎn)法計(jì)算值 static RandomNumber dart; int k=0; for (int i=1;i =n;i+) double x=dart.fRandom(); double y=dart.fRandom(); if (x*x+y*y)=1) k+; return 4*k/double(n); ,22,7.2.2 計(jì)算定積分,（1）用隨機(jī)投點(diǎn)法計(jì)算定積分 設(shè)f(x)是0，1上的連續(xù)函數(shù)，

11、且0f(x)1。需要計(jì)算的積分 為 , 積分 I 等于圖中的面積G。,在圖所示單位正方形內(nèi)均勻地作投點(diǎn)試 驗(yàn)，則隨機(jī)點(diǎn)落在曲線下面的概率為：,假設(shè)向單位正方形內(nèi)隨機(jī)地投入n個(gè) 點(diǎn)(xi，yi)，i = 1,2，n。隨機(jī)點(diǎn)（xi，yi）落入G內(nèi)，則yi f（xi）。 如果有m個(gè)點(diǎn)落入G內(nèi)，則隨機(jī)點(diǎn)落入G內(nèi)的概率，即,23,double Darts (int n) / 用隨機(jī)投點(diǎn)法計(jì)算定積分 static RandomNumber dart; int k=0; for (int i=1;i=n;i+) double x=dart.fRandom(); double y=dart.fRandom()

12、; if (y=f(x) k+; return k/double(n) ,24,7.3 舍伍德算法,25,7.3 舍伍德算法,設(shè)A是一個(gè)確定性算法，當(dāng)它的輸入實(shí)例為x時(shí)所需的計(jì)算時(shí)間記為tA(x)。設(shè)Xn是算法A的輸入規(guī)模為n的實(shí)例的全體，則當(dāng)問題的輸入規(guī)模為n時(shí)，算法A所需的平均時(shí)間為,這顯然不能排除存在xXn使得 的可能性。希望獲得一個(gè)隨機(jī)化算法B，使得對(duì)問題的輸入規(guī)模為n的每一個(gè)實(shí)例均有,這就是舍伍德算法設(shè)計(jì)的基本思想。當(dāng)s(n)與 相比可忽略時(shí)，舍伍德算法可獲得很好的平均性能。,26,7.3.1 隨機(jī)快速算法 7.3.2 隨機(jī)選擇算法 7.3.2 搜索有序表,27,7.3.1 隨機(jī)快速

13、排序算法,隨機(jī)快速排序算法 快速排序算法 算法的核心在于選擇合適的劃分基準(zhǔn) 改變快速排序算法性能不穩(wěn)定，即輸入相關(guān)的問題,28,template void quicksort_random(Type A,int low,int high) random_seed(0);/* 選擇系統(tǒng)當(dāng)前時(shí)間作為隨機(jī)數(shù)種子 */ r_quicksort(A,low,high); /* 遞歸調(diào)用隨機(jī)快速排序算法 */ ,void r_quicksort(Type A,int low,int high) int k; if (lowhigh) k = random(low,high);/* 產(chǎn)生low到high之間

14、的隨機(jī)數(shù)k */ swap(Alow,Ak); /* 把元素Ak交換到數(shù)組的第一個(gè)位置*/ k = split(A,low,high);/* 按元素Alow把數(shù)組劃分為兩個(gè) */ r_quicksort(A,low,k-1);/* 排序第一個(gè)子數(shù)組 */ r_quicksort(A,k+1,high);/* 排序第二個(gè)子數(shù)組 */ ,隨機(jī)快速排序算法,29,最壞時(shí)間復(fù)雜度仍是：O(n2) 最壞情況：當(dāng)隨機(jī)數(shù)發(fā)生器第i次隨機(jī)產(chǎn)生的樞點(diǎn)元素恰恰就是數(shù)組中第i大或第i小的元素時(shí)造成最壞情況 與輸入無關(guān) 情況是微乎其微的 輸入元素的任何排列順序，都不可能使算法行為處于最壞的情況 期望運(yùn)行時(shí)間是O(nl

15、ogn),30,7.3.2 隨機(jī)選擇算法,選擇問題 給定線性序集中n個(gè)元素和一個(gè)整數(shù)1kn，要求找出這n個(gè)元素中第k小的元素,對(duì)選擇問題而言，用中位數(shù)作為劃分基準(zhǔn)可以保證在最壞情況下用線性時(shí)間完成選擇。如果只簡(jiǎn)單地用待劃分?jǐn)?shù)組的第一個(gè)元素作為劃分基準(zhǔn)，則算法的平均性能較好，而在最壞的情況下需要O(n2)計(jì)算時(shí)間。 舍伍德型選擇算法則隨機(jī)地一個(gè)數(shù)組元素作為劃分基準(zhǔn)。這樣既能保證算法的線性時(shí)間平均性能又避免了計(jì)算擬中位數(shù)的麻煩。,31,template Type select(Type a,int l,int k) /計(jì)算al:r中第k小元素 static RandomNumber rnd; wh

16、ile (true) if( l =r) return al; int i = l, j=l + rnd.Random(r- l+1); /隨機(jī)選擇劃分基準(zhǔn) swap(ai,aj); j=r+1; Type pivot=al; /以劃分基準(zhǔn)為軸作元素交換 while (true) while (a+ipivot); if (i=j) break; Swap (ai,aj); ,if (j-l+1=k) return pivot; al=aj; aj=pivot; /對(duì)子數(shù)組重復(fù)劃分過程 if (j-l+1k) k=k-j+l-1; l=j+1; else r=j-1; ,32,由于算法sele

17、ct使用隨機(jī)數(shù)產(chǎn)生器隨機(jī)地產(chǎn)生1和r之間的隨機(jī)整數(shù)。因此，算法select所產(chǎn)生的劃分基準(zhǔn)是隨機(jī)的。在這個(gè)條件下，可以證明，當(dāng)用算法select對(duì)含有n個(gè)元素的數(shù)組進(jìn)行劃分時(shí)，劃分出的低區(qū)子數(shù)組中含有1個(gè)元素的概率為2/n；含有i個(gè)元素的概率為1/n，i=2,3,n-1。設(shè)T(n)是算法select作用于一個(gè)含有n個(gè)元素的輸入數(shù)組上所需的期望時(shí)間的一個(gè)上界，且T(n)是單調(diào)遞增的。在最壞情況下，第k小元素總是被劃分在較大的子數(shù)組中。由此，可以得到關(guān)于T(n)的遞歸式：,33,在上面的推導(dǎo)中，從第一行到第二行是因?yàn)閙ax(1,n-1)=n-1,并且當(dāng)n是奇數(shù)時(shí)，T(n/2),T(n/2+1),T

18、(n-1)在和式中均出現(xiàn)2次；n 是偶數(shù)時(shí)， T(n/2+1),T(n/2+2),T(n-1)均出現(xiàn)兩次，T(n/2)只出現(xiàn)一次。因此，第二行中的和式是第一行中和式的一個(gè)上界。從第2行到第3行是因?yàn)樵谧顗那闆r下T(n-1)=O(n2),故可將T（n-1）/n包含在O(n)中。由此可知，非遞歸的舍伍德型選擇算法可以在O(n)平均時(shí)間內(nèi)實(shí)現(xiàn)。,34,上述舍伍德選擇算法對(duì)確定性選擇算法所做的修改非常簡(jiǎn)單且容易實(shí)現(xiàn)。但有時(shí)所給的確定性算法無法直接改造成舍伍德算法。此時(shí)可借助隨機(jī)預(yù)處理技術(shù)，不改變?cè)械拇_定性算法僅對(duì)其輸入進(jìn)行隨機(jī)洗牌，同樣可收到舍伍德算法的效果。例如，對(duì)于確定性選擇算法，可以用下面的洗

19、牌算法Shuffle將數(shù)組a中的元素隨機(jī)排列，然后用確定性選擇算法求解。這樣做的效果與舍伍德型算法是一樣的。,template void Shuffle (Type a, int n) /隨機(jī)洗牌算法 static RandomNumber rnd; for (int i=0; i n; i+) int j=rnd.Random(n-i)+i; Swap (ai,aj); ,拉斯維加斯( Las Vegas )算法,拉斯維加斯算法的一個(gè)顯著特征是它所作的隨機(jī)性決策有可能導(dǎo)致算法找不到所需的解。,public static void obstinate(Object x, Object y) /

20、 反復(fù)調(diào)用拉斯維加斯算法LV(x,y)，直到找到問題的一個(gè)解y boolean success= false; while (!success) success=lv(x,y); ,設(shè)p(x)是對(duì)輸入x調(diào)用拉斯維加斯算法獲得問題的一個(gè)解的概率。一個(gè)正確的拉斯維加斯算法應(yīng)該對(duì)所有輸入x均有p(x)0。 設(shè)t(x)是算法obstinate找到具體實(shí)例x的一個(gè)解所需的平均時(shí)間 ,s(x)和e(x)分別是算法對(duì)于具體實(shí)例x求解成功或求解失敗所需的平均時(shí)間，則有： 解此方程可得：,36,n后問題,對(duì)于n后問題的任何一個(gè)解而言，每一個(gè)皇后在棋盤上的位置無任何規(guī)律，不具有系統(tǒng)性，而更象是隨機(jī)放置的。由此容易

21、想到下面的拉斯維加斯算法。,在棋盤上相繼的各行中隨機(jī)地放置皇后，并注意使新放置的皇后與已放置的皇后互不攻擊，直至n個(gè)皇后均已相容地放置好，或已沒有下一個(gè)皇后的可放置位置時(shí)為止。,如果將上述隨機(jī)放置策略與回溯法相結(jié)合，可能會(huì)獲得更好的效果?？梢韵仍谄灞P的若干行中隨機(jī)地放置皇后，然后在后繼行中用回溯法繼續(xù)放置，直至找到一個(gè)解或宣告失敗。隨機(jī)放置的皇后越多，后繼回溯搜索所需的時(shí)間就越少，但失敗的概率也就越大。,37,n 皇后問題,問題描述 n皇后問題要求將n個(gè)皇后放在nn棋盤的不同行、不同列、不同斜線的位置，找出相應(yīng)的放置方案 隨機(jī)化措施 對(duì)某行放置皇后的有效位置進(jìn)行隨機(jī) 對(duì)某行所有列位置進(jìn)行隨機(jī),

22、38,n 皇后問題,Class Queen public: friend void nQueen(int); private: bool Place(int k); /測(cè)試皇后k置于第xk列的合法性 bool QueenLV(void); /隨機(jī)放置n個(gè)皇后拉斯維加斯算法 int n, *x,*y; /n表示皇后個(gè)數(shù)，x和y表示解向量 ； Bool Queen:Place(int k) for(int j=1;jk;j+) if(abs(k-j)=abs(x j-xk)|(x j=xk) return false; return true; ,39,對(duì)某行放置皇后的有效位置進(jìn)行隨機(jī)算法 boo

23、l Queen:QueensLV( ) RandomNumber rnd; /隨機(jī)數(shù)產(chǎn)生器 int k=1; /下一個(gè)放置的皇后編號(hào) int count=1;/記錄當(dāng)前要放置的第k個(gè)皇后在第k行的有效位置數(shù) while(k0) count=0; for(int i=1;i0) xk+=yrnd.Random(count); return (count0); /count0表示放置成功 ,40,對(duì)某行所有列位置進(jìn)行隨機(jī)的拉斯維加斯算法 bool Queen:QueensLV1(void) /棋盤上隨機(jī)放置n個(gè)皇后拉斯維加斯算法 RandomNumber rnd; /隨機(jī)數(shù)產(chǎn)生器 int k=1;

24、 /下一個(gè)放置的皇后編號(hào) int count=maxcout;/嘗試產(chǎn)生隨機(jī)位置的最大次數(shù)，用戶根據(jù)需要設(shè)置 while(kn); /kn表示放置成功 ,整數(shù)因子分解,設(shè)n1是一個(gè)整數(shù)。關(guān)于整數(shù)n的因子分解問題是找出n的如下形式的惟一分解式： 其中，p1p2pk是k個(gè)素?cái)?shù)，m1,m2,mk是k個(gè)正整數(shù)。 如果n是一個(gè)合數(shù)，則n必有一個(gè)非平凡因子x，1xn，使得x可以整除n。給定一個(gè)合數(shù)n，求n的一個(gè)非平凡因子的問題稱為整數(shù)n的因子分割問題。,private static int split(int n) int m = (int) Math.floor(Math.sqrt(double)n);

25、 for (int i=2; i=m; i+) if (n%i=0) return i; return 1; ,事實(shí)上，算法split(n)是對(duì)范圍在1x的所有整數(shù)進(jìn)行了試除而得到范圍在1x2的任一整數(shù)的因子分割。,Pollard算法,在開始時(shí)選取0n-1范圍內(nèi)的隨機(jī)數(shù)，然后遞歸地由 產(chǎn)生無窮序列 對(duì)于i=2k，以及2kj2k+1，算法計(jì)算出xj-xi與n的最大公因子 d=gcd(xj-xi，n)。如果d是n的非平凡因子，則實(shí)現(xiàn)對(duì)n的一次分割，算法輸出n的因子d。,private static void pollard(int n) / 求整數(shù)n因子分割的拉斯維加斯算法 rnd = new R

26、andom(); / 初始化隨機(jī)數(shù) int i=1,k=2; int x=rnd.random(n),y=x; / 隨機(jī)整數(shù) while (true) i+; x=(x*x-1)%n; int d=gcd(y-x,n); / 求n的非平凡因子 if (d1) ,對(duì)Pollard算法更深入的分析可知，執(zhí)行算法的while循環(huán)約 次后，Pollard算法會(huì)輸出n的一個(gè)因子p。由于n的最小素因子p ，故Pollard算法可在O(n1/4)時(shí)間內(nèi)找到n的一個(gè)素因子。,蒙特卡羅(Monte Carlo)算法,在實(shí)際應(yīng)用中常會(huì)遇到一些問題，不論采用確定性算法或概率算法都無法保證每次都能得到正確的解答。蒙特

27、卡羅算法則在一般情況下可以保證對(duì)問題的所有實(shí)例都以高概率給出正確解，但是通常無法判定一個(gè)具體解是否正確。 設(shè)p是一個(gè)實(shí)數(shù)，且1/2p1。如果一個(gè)蒙特卡羅算法對(duì)于問題的任一實(shí)例得到正確解的概率不小于p，則稱該蒙特卡羅算法是p正確的，且稱p-1/2是該算法的優(yōu)勢(shì)。 如果對(duì)于同一實(shí)例，蒙特卡羅算法不會(huì)給出2個(gè)不同的正確解答，則稱該蒙特卡羅算法是一致的。 有些蒙特卡羅算法除了具有描述問題實(shí)例的輸入?yún)?shù)外，還具有描述錯(cuò)誤解可接受概率的參數(shù)。這類算法的計(jì)算時(shí)間復(fù)雜性通常由問題的實(shí)例規(guī)模以及錯(cuò)誤解可接受概率的函數(shù)來描述。,蒙特卡羅(Monte Carlo)算法,對(duì)于一個(gè)一致的p正確蒙特卡羅算法，要提高獲得正

28、確解的概率，只要執(zhí)行該算法若干次，并選擇出現(xiàn)頻次最高的解即可。 如果重復(fù)調(diào)用一個(gè)一致的(1/2+)正確的蒙特卡羅算法2m-1次，得到正確解的概率至少為1-，其中，,對(duì)于一個(gè)解所給問題的蒙特卡羅算法MC(x)，如果存在問題實(shí)例的子集X使得： (1)當(dāng)xX時(shí)，MC(x)返回的解是正確的； (2)當(dāng)xX時(shí)，正確解是y0，但MC(x)返回的解未必是y0。 稱上述算法MC(x)是偏y0的算法。,重復(fù)調(diào)用一個(gè)一致的，p正確偏y0蒙特卡羅算法k次，可得到一個(gè)O(1-(1-p)k)正確的蒙特卡羅算法，且所得算法仍是一個(gè)一致的偏y0蒙特卡羅算法。,主元素問題,設(shè)T1:n是一個(gè)含有n個(gè)元素的數(shù)組。當(dāng)|i|Ti=x

29、|n/2時(shí)，稱元素x是數(shù)組T的主元素。,public static boolean majority(intt, int n) / 判定主元素的蒙特卡羅算法 rnd = new Random(); int i=rnd.random(n)+1; int x=ti; / 隨機(jī)選擇數(shù)組元素 int k=0; for (int j=1;jn/2); / kn/2 時(shí)t含有主元素 ,public static boolean majorityMC(intt, int n, double e) / 重復(fù) 次調(diào)用算法majority int k= (int) Math.ceil(Math.log(1/e)/Math.log(2); for (int i=1;i=k;i+) if (majority(t,n) return true; return false; ,對(duì)于任何給定的0，算法majorityMC重復(fù)調(diào)用log(1/) 次算法majority。它是一個(gè)偏真蒙特卡羅算法，且其錯(cuò)誤概率小于。