《算法技术手册》一2.3.2 平均情况

2.3.2 平均情况

考虑设计一个支持n个电话的电话系统，其中n是一个非常大的数——要求在最坏情况下，系统必须能够完成n/2位用户同时呼叫另外n/2位用户。虽然这个系统永远不会由于过载而崩溃，但构造它还是需要花费很高的代价。因为现实生活中，n/2位用户同时呼叫另外n/2位用户发生的概率极小。相反，我们可以设计一个非常容易构建的系统，并借助数学工具来计算由过载导致的系统崩溃的概率。
对于规模为n的样本集合，我们用一个概率分布Pr{si}表示样本分布的概率。其中，单个样本的出现概率为0到1，所有样本的概率的和为1。更加正式一点的定义为，如果Sn是所有规模为n的样本集合，那么：

如果t()表示算法在单个样本上的执行时间，那么在Sn上的平均执行时间是：

也就是说，样本si的实际执行时间t(si)会与它作为输入数据的概率加权。如果Pr{si}=0，那么t(si)的实际值将不会影响程序的期望执行时间。我们用Tac(n)表示算法在Sn上的平均执行时间，那么Tac(n)的增长率则表示算法在平均情况下的复杂度。
回忆一下，在描述工作量和时间的增长率时，我们总是会忽略常数，因此顺序搜索n个元素平均情况需要次查找（这符合之前的假设）。按照惯例，在符合这些假设的前提下，顺序搜索需要检查线性数量或者说n阶的元素。