概述
特点
- 不要求算法对所有可能的输入均正确计算
- 只要求出现错误的可能性小到可以忽略的程度
- 不要求对同一输入，算法每次执行时给出相同的结果
很快获得相当可信的结果
应用
分布式计算、通信、信息检索、计算几何、密码学
公开密钥体系、RSA算法
优点
- 对于某一给定的问题，随机算法所需的时间与空间复杂性，往往比当前已知的、最好的确定性算法要好
- 理解和实现上都简单
- 避免去构造最坏情况的例子
算法
Las Vegas算法
- 出现求不出解的情况，但一旦找到，这个解一定正确
- 在求不出解时，需再次调用算法进行计算，直到获得解为止
- 对于此类算法，主要是分析算法的时间复杂度的期望值，以及调用一次产生失败（求不出解）的概率
Monte Carlo算法
- 通常不能保证计算出来的结果总是正确的，一般只能断定所给解的正确性不小于p （ 1/2＜p＜1）
- 算法的反复执行能够使发生错误的概率小到可以忽略的程度
- 由于每次执行的算法是独立的，故k次执行均发生错误的概率为(1-p)^k
- 对于判定问题（回答只能是“Yes”或“No”）：带双错（回答”Yes”或”No”都有可能错）、带单错（只有一种回答可能错）
Las Vegas算法可以看成是单错概率为0的Monte Carlo算法
在不允许发生错误的应用中，Monte Carlo算法不可以使用。若小概率的出错允许的话，Monte Carlo算法比Las Vegas算法要节省许多时间
典型例题
找第k小元素的随机算法
在n个数中随机的找一个数A[i]=x, 然后将其余n-1个数与x比较，分别放入三个数组中：S1(元素均<x), S2(元素均=x), S3(元素均＞x)
|S1|≥k ，Select(k,S1)
（|S1|+|S2|）≥k，则第k小元素就是x
（|S1|+|S2|）＜ k，Select(k-|S1|-|S2|,S3)
定理：若以等概率方法在n个数中随机取数，则该算法用到的比较数的期望值不超过4n
Sherwood随机化方法(Las Vegas)
如果某个问题已经有了一个平均情况下较好的确定性算法，但是该算法在最坏情况下效率不高，此时引入一个随机数发生器
如果算法（所给的确定性算法）无法直接使用Sherwood方法，则可以采用随机预处理的方法，使得输入对象服从均匀分布
Testing String Equality(（Monte Carlo算法)
设A处有一个长字符串x（e.g. 长度为106），B处也有一个长字符串y，A将x发给B，由B判断是否有x=y
由A发一个x的长度给B，若长度不等，则x≠y
长度相等，则采用“取指纹”的方法：
1.A对x进行处理，取出x的“指纹”，然后将x的“指纹” 发给B
2.由B检查x的“指纹”是否等于y 的“指纹”
3.若取k次“指纹”（每次取法不同），每次两者结果均相同，则认为x与y是相等的
4.随着k的增大，误判率可趋于0
令I(x)是x的编码，取Ip(x) ≡ I(x) (mod p)作 为x的指纹，p是一个小于M的素数，M可根据具体需要调整
错判率分析
Ip(x)=Ip(y)而x≠y，则称此种情况为一个误匹配
Pr[failure] = （使得误匹配的p的个数）／（小于M的素数的总个数）
k次试验误匹配的概率小于 1/n^(k),当n较大、且重复了k次试验时，误匹配的概率趋于0
Pattern Matching(Monte Carlo)
给定两个字符串：X=
,…,
，Y=
,…,
， 看Y是否为X的子串？
X(j)=x(j)x(j＋1)…x(j+m-1) 从X的第j位开始、长度与Y一样的子串
从j=1开始到j=n-m+1，逐一比较Ip（X(j)）与Ip（Y）
1.随机取一个小于M的素数p，j=1
2.计算Ip(Y)、Ip(X(1))及Wp(=2m mod p)
3.While (j≤n-m+1) {
if(Ip(X(j))=Ip(Y))
return j;
else{
根据Ip(X(j))计算出Ip(X(j+1);
j++;
}
}
return 0;
错判率分析
当Y≠X(j)，但Ip(Y)=Ip(X(j))时产生失败
率Pr[failure]<1/n，即失败的概率只与X的长度有关，与Y的长度无关
备注
当Ip(Y)=Ip(X(j))时，不直接return j，而去比较Y和X(j)，转成Las Vegas算法
Random Sampling问题(Las Vegas)
设给定n个元素(为1，2，…n),要求从n个数中随机地选取m个数（m≤n）
长为n的布尔数组B来标识i是否被选中,初始时均为false
随机产生〔1，n〕之间的一个整数i，若B[i]==false，则将i加入被选中队列，B[i]=true
反复执行直到m个不同的数全部被选出为止
改进
- 当n和m很接近时，产生最后几个随机数的时间可能很长
当m>n/2时，先去生成(n-m)(<n/2)个随机数，然后再取剩下的m个数作为选出的数 - 当n与m相比大很多时（例：n﹥m2），布尔数组B对空间浪费很多
用一个允许冲突的、长为m的散列表，来存放产生的随机数
分析
：在j-1个数已经选出的前提下，当前随机产生的数是以前尚未选过的数的概率
=(n-j+1)/n
:前随机产生的数是以前选过的j-1个数之一的概率
=1- p(j)=(j-1)/n
随机变量Xj:在j-1个数已经选出后，再去找出第j个不同的数时，所需要产生的整数个数
服从几何分布，E(
)=1/
Y表示从n个数中选出m个数时（m≤ n/2），所需产生的整数个数的总和的随机变量（目标）
Y=＋
＋
＋…＋
E(Y)≤1.69n
T(n)正比于算法产生整数的个数总和Y
主元素问题(Monte Carlo)
设T[1:n]是一个含有n个元素的数组。当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素
public static boolean majority(int[]t, int n){
rnd = new Random();
int i=rnd.random(n)+1;
int x=t[i]; // 随机选择数组元素
int k=0;
for (int j=1;j<=n;j++){
if (t[j]==x) k++;
return (k>n/2); // k>n/2 时t含有主元素
}
}
public static boolean majorityMC(int[]t, int n, double e){
int k= (int) Math.ceil(Math.log(1/e)/Math.log(2));
//重复多次调用算法majority,计算时间和调用的次数相关
for (int i=1;i<=k;i++){
if (majority(t,n)) return true;
}
return false;
}
素数测试问题
判断一个数是否为素数
费尔马（ Fermat ）小定理
若n为素数，且0<a<n，有a^(n-1)≡1(mod n)
逆定理不成立，但反例不多，特别是当n很大且又是随机选取的时候
二次探测定理
如果p是一个素数，且0<x<p，则方程x^2 ≡ 1(mod p)的解为x=1，p-1
