数值随机算法
这类算法常用于数值问题的求解。 得到的往往是近似解，而近似解的精度与计算时间正相关。
E.g. 用投点方式计算圆的面积
圆半径已知。 设想一个将整个圆包括其中的矩形，面积已知。 在矩形内随机投入一定数量的点，对每个点检测是否在圆内。
通过计算在圆内的点的数量比上投点的总量是圆占矩形的比例。再乘以矩形面积可得圆的面积。
舍伍德算法
我们知道一些算法对特定的输入会有不同的效率表现（我记得这类算法被称为输入敏感型算法）。
一个经典的例子是快速排序。对于接近有序的输入，快速排序的效率会退化到O(n ^ 2)的水平。 好在一般来说，这类坏例子所占比例不大。如果我们的输入数据是完全随机的，效率表现还是可以的。
实际应用时的数据集其实不太可能符合完全随机的要求，更有可能是在输入空间内局部聚集的。 一种解决办法是消除特定数据与算法表现之间的关系。在算法过程中引入随机。这就是舍伍德算法的思想。
E.g. 随机化快速排序
快速排序算法中的特定数据与算法表现之间的关系是通过固定的轴点选取引起的。
当我们始终选取第一个元素作为轴点，则算法对于已排序的数据退化。 如果我们随机选取轴点，则不会有一个固定输入实例与退化情形关联。
注意，在具体运行时仍有可能会出现一个输入实例和一个随机轴点序列一起发生退化，但此时这种退化不针对具体输入空间，即算法已对输入不敏感。
E.g. 跳跃表
拉斯维加斯算法
拉斯维加斯算法是一种搜索解的算法，类似于贪心算法，不想通过完备的计算得出一个局部决策的解。 对此，拉斯维加斯算法的解决方法是引入随机决策。
引入随机决策直接导致算法的准确性下降，这一点可以由得到了巨大提升的算法效率来弥补，也就是多运行几次。 另一方面，可以采用混合策略：通过随机决策迅速缩小搜索空间，到达某一阀值后改用完全的搜索。
E.g. : Pollard整数分解
蒙特卡罗算法
蒙特卡罗算法与拉斯维加斯算法相似，通过在搜索过程中引入随机决策来提高算法的效率。 与拉斯维加斯算法不同的是：
- 拉斯维加斯算法可以给出问题的准确解，或者告知算法没有找到解
- 蒙特卡罗算法只给出概率意义上的解，即给出的解有p的概率是正确的
多次应用蒙特卡罗算法可以快速提高算法正确的概率。例如，如果算法的正确解是唯一的，一次运行可以得出一个1 / 2正确的答案。如果算法运行n次的结果都是x，则x为正解的概率为1 - (1 / 2) ^ n。
由此可见，蒙特卡罗算法比较适用于判定问题，我们可以用一个p正确的随机决策来代替确定的判定算法，而运行随机决策足够多次就可以得出极可能正确的答案。
E.g. 寻找主元素
对于一个存在主元素的数组，主元素是这个数组中出现次数过数组大小一半的元素。
我们可以在数组中任选一个，（对于主元素存在的数组）它是主元素的概率至少是1 / 2。 此时我们扫描整个数组，可以判断其是否是主元素，这个算法有超过1 / 2的概率找到主元素，并且它找到的一定是主元素。
如果我们重复运行上述算法常数(c)次，得到一个O(n)的算法，有1 - (1 / 2) ^ c的可能性正确。
PS:寻找主元素存在O(n)的确定算法，参考《编程之美》
E.g. ：素性测试
Read full article from 图灵社区 : 阅读 : 随机化算法
