随机算法

### 1. 数值随机算法 通过随机点数求解圆周率，定积分等问题。 主要利用大数定律与强大数定律。 ### 2. 拉斯维加斯随机算法(Las Vegas) 通过随机选择法求解集合S中的第k小的数 算法得到的解一定是正确解，但算法也可能不获得问题的解，满足以上条件即为拉斯维加斯算法。 ### 3. 舍伍德随机算法(Sherwood) 随机快速排序 舍伍德算法能够获得问题的正确解，它的精髓在于消除算法的最坏情况与特定实例之间的关联（例如，快速排序最坏时间复杂度为O(n方)） 3. 蒙特卡洛随机算法(Monte Carlo) a算法并不总能获得问题的正确解 b算法以较高的概率获得正确解 c不存在有效过程判定算法输出的解是否为问题的正确解 满足以上三条性质的算法称为蒙特卡洛算法。