蒙特卡罗(Monte Carlo)算法

设蒙特卡罗算法是一致的p正确的。那么至少需调用多少次，使得蒙特卡罗算法得到正确解的概率不低于1-ε？

主元素问题

T[1:n]含有n个元素，当|{i|T[i]=x}|>n/2时，称元素x是数组T的主元素。
Template<class Type>
bool majority(Type T[], int n) //判定主元素的蒙特卡罗算法
{ 
RandomNumber rnd;
int i=rnd.random(n)+1; //产生1~n之间的随机下标
Type 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含有主元素
}
//时间复杂性是O(n);

拉斯维加斯算法

一个显著特征是其所做的随机性决策有可能导致算法找不到解。一旦使用拉斯维加斯算法找到一个解，则这个解就一定是正确的。找到解的概率随着所用计算时间的增加而提高。 

典型调用形式为：bool success = LV(x, y)。 LV为算法名称，x为问题的输入。 当success为true时，y为问题的解；当success为false时，算法未能找到问题的一个解。此时可对同一个实例再次独立地调用相同的算法，以提高找到解的概率。

舍伍德 (Sherwood) 算法

总能求得问题的一个解，且所求得的解总是正确的。 当一个确定性算法在最坏情况下的计算复杂性与在平均情况下的计算复杂性有较大差别时，可以在这个确定性算法中引入随机性将其改造成一个舍伍德算法，消除或减少问题的好坏实例之间的这种性能上的显著差异。

快速排序算法：

由于该算法需选定一个基准元素，而通常是选择待排序序列的某个固定的元素（如第一个、最后一个、中间一个、或三者的中位数等），这就造成该算法在最坏情况下的时间复杂性与平均情况下的差别较大。

如要消除上述的差异性，必须在基准元素的选择上多做考虑。如在基准元素选择时引入随机性，即随机地选择基准元素。

基于舍伍德方法的随机快速排序算法：
QUICK-SORT(A, low, high)
  if low < high
    then pivotpos = RAND-PARTITION(A,low,high) //划分序列
            QUICK-SORT(A,low,pivotpos-1) //对左区间递归排序 
            QUICK-SORT(A,pivotpos+1,high) //对右区间递归排序

    RANDPARTITION(A, low, high)
      RandomNumber rnd
      i = RandomNumber.random(high-low+1) + low
      SWAP(a[low], a[i])
      j = PARTITION(A, low, high)
      return j