平均情况分析

概述

平均情况分析 是对算法在所有可能输入上的期望运行时间进行分析，需要假设输入的概率分布。

定义

平均情况运行时间

设输入空间为 ${\mathcal{I}}_n$，每个输入 $I\in {\mathcal{I}}_n$ 出现的概率为 $\mathrm{Pr}[I]$，则平均运行时间为： $T_{\text{avg}}(n)={\sum }_{I\in {\mathcal{I}}_n}\mathrm{Pr}[I]\cdot T(I)$

核心性质

• 平均情况分析需要对输入分布做出假设（如均匀分布），结果的可靠性依赖于假设的合理性。
• 在缺乏先验知识时，通常假设所有输入等概率出现。
• 平均情况时间复杂度可能优于最坏情况（如快速排序平均 $\Theta (n\lg n)$，最坏 $\Theta (n^2)$）。
• 分析过程通常比最坏情况更复杂，涉及概率论与期望值的计算。

章节扩展

第2章：入门

• 2.2 算法分析 中指出，平均情况分析需要概率假设，而最坏情况分析无需此类假设，因此更通用。
• 插入排序在输入均匀随机排列时，平均比较次数为 $n(n-1)/4$。

参见

• 最好情况分析
• 随机化算法
• 渐近记号