概率分析
概述
概率分析 是一种算法分析技术，在不改变算法本身的前提下，假设输入服从某种概率分布，从而分析算法的期望运行时间或其他性能指标。
定义
概率分析
概率分析使用概率论的工具来分析算法的运行时间或资源消耗。分析时假设输入来自某种概率分布（如均匀分布），然后计算算法性能的期望值。算法本身是确定性的，分析中引入的随机性来自于对输入分布的假设。
核心性质
- 概率分析 vs. 随机化算法：这是两个不同的概念，容易混淆：
- 概率分析是一种分析技术——算法本身是确定性的，我们假设输入服从某种分布来分析其期望行为。
- 随机化算法是一种算法设计技术——算法自身引入了随机性，使得对任何输入都能获得良好的期望性能。
- 适用场景：当输入分布已知或可以合理假设时（如输入均匀随机），概率分析可以提供比最坏情况分析更精确的性能评估。
- 局限性：如果实际输入分布与分析假设的分布不一致，概率分析的结论可能不适用。
- 核心工具：指示器随机变量 和 期望的线性性 是概率分析的两个核心数学工具。
章节扩展
第5章：概率分析与随机化算法
- 5.1 雇佣问题 是概率分析的入门案例：假设候选人以随机顺序到达，分析雇佣问题的期望费用为 。
- 5.3 随机化算法 对比了概率分析与随机化算法的区别，说明随机化如何将概率保证内化到算法中。
- 8.4 桶排序 假设输入均匀分布在 上，通过概率分析证明期望运行时间为 。