算法设计与分析 第五章.ppt

第五章 随机算法 5.1 随机算法的一般性原理 5.2 应用 5.3 随机算法的性能分布 所谓随机算法(randomized algorithm) 就是在执行过程中要做出随机选择的算法 随机算法有两个优势简单和快速 随机算法有两种不同类型 其一是总能给出正确的解两次运行之间唯一的区别是运行时间不同我们把这种随机算法叫做Las Vegas算法 其二是有时会产生不正确解的算法然而我们能够界定产生不正确