首页 » 算法技术手册 » 算法技术手册全文在线阅读

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

关灯直达底部

现在要设计一个支持n个电话的电话系统,n是一个非常大的数目,要求在最坏情况下,即n/2位用户同时呼叫另外n/2位用户时,这个系统也能够正确地处理数据。虽然这个系统不会由于过载而崩溃,但需要花费过高的代价构造这样的情况。而且,n/2位用户同时呼叫另外n/2位用户发生的概率极小。也许可以设计一个花费较小的系统在过载的情况下很少会(或者从不)崩溃。但是我们还是必须借助数学工具来计算这个概率问题。

对于一个n个样本的数据集合,我们用一个概率分布Pr表示样本的出现概率,单个样本的出现概率为0到1,所有样本的概率的和为1。如果Sn是n个样本的数据集合,那么:

如果t表示算法在单个样本的执行时间,那么在Sn上的平均运行时间是:

也就是说,在样本si的实际执行时间,t(si)将会与概率加权。如果Pr{si}=0,那么t(si)的实际值将不会影响程序的期望运行时间。我们用Tac(n)表示算法在Sn上的平均运行时间,那么Tac(n)的增长率表示算法在平均情况下的复杂度。

回忆一下,当我们描述时间或者工作量的增长率时,我们一直忽视了常数,所以我们认为顺序搜索n个元素的平均情况为:

探测(符合我们之前的假设),按照惯例,在符合这些假设的前提下,期望顺序搜索能够处理线性或者是n阶的元素。