第9章 随机算法9.1 概率论预备知识9.2 对随机快速排序算法的分析9.3 随机算法的分类及其局限性 9.3.1 拉斯维加斯型随机算法 9.3.2 蒙特卡洛型随机算法 9.3.3 随机算法的局限性9.4 素数检验和多项式恒等检验 9.4.1 素数检验 9.4.2 多项式恒等检验9.5 随机游动算法 9.5.1 有限马氏链及其表示 9.5.2 求解二元布尔可满足问题的随机游动算法 9.1 概率论预备知识 事件、概率、分布 独立、条件概率 期望、方差 马尔科夫、詹森、契比雪夫不等式 并的界、切诺夫界. 有限概率空间 有限概率空间 存在着有穷个基本事件 每个基本事件发生的概率是0,1 中的数 所有基本事件的概率之和等于1 例子 抛掷一枚均匀硬币 基本事件：正面向上，反面向上 各自概率都为 1/2 抛掷一枚均匀的六面骰子 基本事件：得到 1、2、3、4、5、6点之一 概率各为 1/6事件与概率 事件及其概率 一些基本事件的组合称为事件 事件发生的概率等于其中基本事件的概率之和 例子 抛掷一枚均匀的六面骰子，掷骰子得到偶数这一事件，由2、4、6点这三个基本事件组成，概率为 1/6+1/6+1/
