概率算法可在很大程度上降低算法的复杂度。
概率算法的一个基本特征是对所求解问题的同一实例用同一概率算法求解两次可能得到完全不同的效果。概率算法大致分为四类:数值概率算法，蒙特卡罗（Monte
Carlo）算法，拉斯维加斯（Las Vegas）算法和舍伍德（Sherwood）算法。
1，数值概率算法常用于数值问题的求解,所得到的往往是近似解。
2，蒙特卡罗算法用于求问题的准确解。
3，拉斯维加斯算法不会得到不正确的解，一旦用拉斯维加斯算法找到一个解，那么这个解肯定是正确的。但是有时候用拉斯维加斯算法可能找不到解。与蒙特卡罗算法类似。拉斯维加斯算法得到正确解的概率随着它用的计算时间的增加而提高。对于所求解问题的任一实例，用同一拉斯维加斯算法反复对该实例求解足够多次，可使求解失效的概率任意小。
4，舍伍德算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大差别时，可以在这个确定算法中引入随机性将它改造成一个舍伍德算法，消除或减少问题的好坏实例间的这种差别。舍伍德算法精髓不是避免算法的最坏情况行为，而是设法消除这种最坏行为与特定实例之间的关联性。
在现实计算机上无法产生真正的随机数，因此在概率算法中使用的随机数都是一定程度上随机的，即伪随机数。 产生随机数最常用的方法是线性同余法。由线性同余法产生的随机序列a1,a2,...,an满足
a0=d
an=(ban-1+c)mod m n=1,2.......
其中,b>=0, c>=0, d>=m。d称为该随机序列的种子。
下面我们建立一个随机数类RadomNumber，该类包含一个由用户初始化的种子randSeed。给定种子之后，既可产生与之相应的随机数序列。randseed是一个无符号长整型数，既可由用户指定也可由系统时间自动产生。
const unsigned long maxshort=65536L;
const unsigned long multiplier=1194211693L;
const unsigned long adder=12345L;
class RandomNumber
{
private:
//当前种子
unsigned long randseed;
public:
//构造函数，缺省值0表示由系统自动产生种子
RandomNumber(unsigned long s=0);
//产生0-n-1之间的随机整数
unsigned short Random(unsigned long n);
//产生[0，1)之间的随机实数
double fRandom(void);
};
RandomNumber::RandomNumber(unsigned long s)
{
if(s==0)
randseed=time(0);
else
randseed=s;
}
unsigned short RandomNumber::Random(unsigned long n)
{
randseed=multiplier*randseed+adder;
return (unsigned short)((randseed>>16)%n);
}
double RandomNumber::fRandom(void)
{
return Random(maxshort)/double(maxshort);
}
函数Random在每次计算时，用线性同余式计算新的种子。它的高16位的随机性较好，将randseed右移16位得到一个0-65535之间的随机整数然后再将此随机整数映射到0-n-1范围内。
对于函数fRandom,先用Random(maxshort)产生一个0-(maxshort-1之间的整型随机序列)，将每个整型随机数除以maxshort，就得到[0，1）区间中的随机实数。
下面来看看数值概率算法的两个例子：
1.用随机投点法计算π
设有一半径为r的圆及其外切四边形，如图所示。向该正方形随机投掷n个点。设落入圆内的点在正方形上均匀分布，因而所投入点落入圆内的概率为πr^2/4r^2，所以当n足够大时，k与n之比就逼近这一概率，即π/4。由此可得使用随机投点法计算π值的数值概率算法。具体实现时，只需要在第一次象限计算即可。
double Darts(int n)
{
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);
}
再简单举个舍伍德算法的例子。
我们在分析一个算法在平均情况下的计算复杂性时，通常假定算法的输入数据服从某一特定的概率分布。例如，在输入数据是均匀分布时，快速排序算法所需的平均时间是O(n
logn)。但是如果其输入已经基本上排好序时，所用时间就大大增加了。此时，可采用舍伍德算法消除算法所需计算时间与输入实例间的这种联系。
在这里，我们用舍伍德型选择算法随机的选择一个数组元素作为划分标准。这样既能保证算法的线性时间平均性能又避免了计算拟中位数的麻烦。非递归的舍伍德型算法可描述如下：
template<class Type>
Type select(Type a[], int l, int r, int k)
{
static RandomNumber rnd;
while(true){
if(l>=r)
return a[l];
int i=l, j=l=rnd.Random(r-l+1);
Swap(a[i], a[j]);
j=r+1;
Type pivot=a[l];
while(true)
{
while(a[++i]<pivot);
while(a[--j]>pivot);
if(i>=j)
break;
Swap(a[i], a[j]);
}
if(j-l+1==k)
return pivot;
a[l]=a[j];
a[j]=pivot;
if(j-l+1<k)
{
k=k-j+l-1;
l=j+1;
}
else
r=j-1;
}
}
template <class Type>
Type Select(Type a[], int n, int k)
{
if(k<1||k>n)
throw OutOfBounds();
return select(a, 0, n-1, k);
}
平时我们一般开始考虑的是一个有着很好平均性能的选择算法，但在最坏情况下对某些实例算法效率较低。这时候我们用概率算法，将上述算法改造成一个舍伍德型算法，使得该算法对任何实例均有效。
不过在有些情况下，所给的确定性算法无法直接改造成舍伍德型算法。这时候就可以借助随机预处理技术，不改变原有的确定性算法，仅对其输入进行随机洗牌，同样可以得到舍伍德算法的效果。还是刚才的例子，换一种方法实现：
template<class Type>
void Shuffle(Type a[], int n)
{
static RandomNumber rnd;
for(int i=1;i<n;i++){
int j=rnd.Random(n-i)+i;
Swap(a[i], a[j]);
}
}
在上文里，我们对概率算法中的数值概率算法以及舍伍德算法举例作了简要的介绍，希望能使大家对概率算法有一个初步的认识，并且将这种思想运用到自己平时的编程中。
