[TOC] # 概述 Randomization is a fundamental technique in algorithm design,that allows programs to run quickly when the average-case behavior of an algorithm is better than the worst-case behavior. It is also heavily used in games,both in entertainment and gambling. 当算法的平均时间比最坏情况下所用的时间少时，我们可以用随机化算法进行改进。 随机化算法是这样一种算法，在算法中使用了随机函数，且随机函数的返回值直接或者间接的影响了算法的执行流程或执行结果。随机化算法基于随机方法，依赖于概率大小。 # 随机化算法分类 一般情况下，可以将随机化算法分为四类： * 数值随机化算法 * 蒙特卡罗算法 * 拉斯维加斯算法 * 舍伍德算法 #### 数值随机化算法 这种算法常用于数值问题的求解。这类算法得到的往往是近似解。 #### 蒙特卡罗算法 用于求问题的准确解。对于许多问题，近似解毫无意义。 #### 拉斯维加斯算法 不会得到不正确的解。 #### 舍伍德算法 该算法总能求得问题的一个解，且所求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其平均情况下的计算复杂性有较大差别时，可在这个算法中引入随机性将它改造成为一个舍伍德算法，消除或者减少问题的好坏实例间的这种差别。舍伍德算法的精髓不是避免算法的最坏情形行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。