开头讨论的动态规划算法、回溯法、分支定界算法、二分法等都是针对每个计算步骤确定的算法，但是这次讨论的是随机化算法，算法运行中可以随机选择下一个计算步骤
随机化算法不一定是最优的，也不一定是正确的，但它一定是最快的，可以大大降低算法的复杂度。
随机化算法的基本特征之一是，对所解问题的同一实例用同一随机化算法求解两次可能会得到完全不同的结果。
随机化算法可分为四类：数值随机化、蒙特卡罗算法、拉斯维加斯算法和舍伍德算法。 这次主要是数值随机化算法和舍伍德算法
数值随机化算法数值随机化算法常用于解决数值问题，得到的是近似解，近似解的精度随着计算时间的增加而提高。 大多数情况下，不可能或不需要计算问题的精确解，所以使用数值随机化算法可以得到相当满意的解。
随机数
随机数在随机化算法中起着非常重要的作用。 由于现实中的计算机无法产生真随机数，随机化算法中使用的随机数都在一定程度上是随机的，即伪随机数。 线性合并法是生成伪随机数最常用的方法。 基于线性联合法的随机序列a1，a2，a3，an满足以下条件：
a0=Dan=(ban-1c ) mod Mn=1，2， 式中，b=0，c=0，d=m。 D被称为该随机序列的种子，如何选择该方法中的常数b、c、m直接关系到所谓的原始随机序列的随机性能，这是随机性能理论研究的内容。
直观上，因为m应该足够大，所以m需要作为机器的数量，并且gcd(m，d )=1，所以d可以是质数。
创建包含用户要初始化的种子randSeed的随机数系统RandomNumber。 给定初始种子，将生成相应的随机序列。 种子randSeed是无符号整数，可以由用户选择，也可以在系统时间自动生成。 函数Random ) )的输入参数n=65535是无符号整数，返回0到n-1之间的随机整数。 函数fRandom ()返回0到1之间的随机实数。
# include iostream # include time.h # includeiomanipusingnamespacestd； //随机数系constunsignedlongmaxshort=65536 l； constunsignedlongmultiplier=1194211696 l； const unsigned long adder=12345L； classrandomnumber { private : unsigned long randseed； //现有种子//用线性综合法构造新种子，其高16位随机性好。 将randomSeed向右移位16位，以获得0到0~65535的随机整数//，并将该随机整数映射到0到n-1范围内的公共3360随机符号/生成//生成(0，1 )之间的随机整数Doublefrandom(void )的随机实数)； randomnumber :3360 randomnumber (unsigned longs )//生成种子if (s==0) randSeed=time(0) 0； //按系统时间生成种子的else randSeed=s； //用户提供种子(unsignedshortrandomnumber 3360: random ) unsignedlongn ) (0到n-1之间的随机整数randseed=multiplier * randsed } doublerandomnumber :3360 f random (void )//0~1到1之间的随机整数return random (max short )/double (max short )； }用实际例子说明随机数的应用场景吧。
在利用伪随机数模拟投硬币的实验中，假设投了10次硬币，每次投硬币都能得到正反是随机的。 扔10次硬币组成事件，调用random(2)返回二值结果。 0表示里，1表示表。 模拟了10次投硬币事件50000次，计算了点数向上的次数分别为0、1、2…、10次时为多少。
//模拟随机扔10次硬币，random(2)返回2值结果：0表示反面，1表示表//TossCoins模拟扔10次硬币的时间，在主程序中函数TossCoins for(I=
0;i < numberCoins;i++) tosses += coinToss.Random(2); return tosses;}//测试程序int main(){ const int NCOINS = 10; const long NTOSSES = 50000L; //heads[i]是得到i次正面的次数 long i,heads[NCOINS+1]; int j,position; for(j = 0;j < NCOINS + 1;j++)//初始化head数组 heads[j] = 0; for(i = 0;i < NTOSSES;i++)//重复50000次模拟事件 head[TossCoins(NCOINS)]++; for(i = 0;i < NCOINS;i++) { //输出频率图 position = int(float(heads[i]) / NTOSSES * 72); cout<<setw(6)<<i; for(j = 0;j < position - 1;j++) cout<<" "; cout<<"*"<<endl; } return 0;}结果应如下:
设一半径为r的圆及其外切四边形，向该正方形随机地投掷n个点。设落入圆内的点数为k，由于所投入的点在正方形上均匀分布，因而所投入的点落入圆内的概率为:
所以当n足够大时，k与n之比就逼近这一概率，即Π/4，从而Π≈4k/n。由此可得用随机投点法计算Π值的数值随机化算法。同理，定积分问题也可以利用随机投点法来计算。
随机数还可以用来解决非线性方程组，在这里我们就不具体介绍了，大致思路是，构造一个目标函数，目标函数的极小值点即使所求非线性方程组的一组解。
在求根区域内，选定一个x0作为一个选取随机点x，计算目标函数，并把满足精度要求的随机点x作为所求非线性方程组的近似解。
在指定的求根区域D内，选一个随机点x0当作随即搜索的出发点。在搜索过程中，假设第j步随机搜索得到的随机搜索点为xj。在第j+1步，先计算下一步的随机搜索方向r，再计算搜索步长a,由此可以得到第j+1步的随机搜索增量Δxj。从当前点xj依随机搜索增量Δxj得到第j+1步的随机搜索点xj+1 = xj + Δxj。
当目标函数足够小的时候(因为非线性方程组要求等式等于0)，取xj+1为所求非线性方程组的近似解，否则进行下一步新的随机搜索过程。
舍伍德算法总能求得问题的一个解，且求得的解总是正确的。当一个确定性算法在最坏情况下的计算复杂性与其在平均情况下的计算复杂性有较大的差异时，可在这个确定性算法中引入随机性将它改为一个舍伍德算法，从而消除或者减少问题的好坏实例间的这种差别。
舍伍德算法的精髓不是避免算法的最坏情形行为，而是设法消除这种最坏情形行为与特定实例之间的关联性。
假如有一确定性算法A，A是固定的，所以我们每次在A算法中的每一步选择都是固定好的，有章法可循的。
但是现在又有一算法B，算法B在每一步是可以随机选择的，因此它就可以优化时间复杂度。
随机选择的时间时间复杂度应该是一个平均值，所以这个时间复杂度可以消除或者减少最坏情况与实例的关联性。否则我们总会产生一种固定的形式，浪费巨大的时间，这就是我们的最坏情况。但是如果我们采用随机选择的方法，可以有效降低这种情况的概率。
线性时间选择算法我们在之前讨论分治法的时候已经讨论过了，我们会在所以数列中选出中位数，再在所有中位数中选出中位数，以这个中位数为基准划分。
但是在随机化版本中，用拟中位数作为划分基准可以保证在最坏情况下用线性时间完成选择。如果只简单地用待划分数组的第一个元素作为划分基准，则算法的平均性能较好，而在最坏情况下需要O(n^2)计算时间。
舍伍德选择算法则随机地选择一个数组元素作为划分基准，这样既能保证算法的线性时间平均性能，也避免了计算拟中位数的麻烦。
舍伍德思想还可以用于设计高效的数据结构，跳跃表就是一例。提高有序链表效率的一个技巧是在有序链表的部分结点处增设附加指针以提高其搜索性能。在增设附加指针的有序链表中搜索一个元素时，可借助附加指针跳过链表中的若干节点，加快搜索速度。这种增加了向前附加指针的有序链表称为跳跃表。应在跳跃表的哪些结点增加附加指针，以及在该结点处应增加多少指针完全采用随机化方法确定。这使得跳跃表可在O(logn)平均时间内支持有序集的搜索、插入和删除等运算。
为了在动态变化中维持跳跃表中附加指针的平衡性，必须使跳跃表中k级结点数维持在总结点数的一定比例范围内。在一个完全跳跃表中，50%的指针式0级指针，25%式1级指针，…，(100/2^(k+1))%的指针是k级指针。
因此插入一个元素的时候，1/2的概率插入一个0级结点，1/4的概率插入一个1级结点，…，以概率1/2^(k+1)引入一个k级结点**。舍伍德算法就是为跳跃表中每个结点的级数做随机**。