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

《算法技术手册》分析

关灯直达底部

在例4-11的sortPointers函数中,输入中的每一个元素根据提供的散列函数,被插入到相应的桶中,花费是线性时间O(n)。桶中的元素并不是有序的,但是由于仔细设计的散列函数,我们知道,如果i<j,在桶bi中的所有的元素都小于bj中的所有元素。

随着值从桶中抽取出来并且写回到输入数组,当一个桶包含多个元素的时候就要使用插入排序。对于表现出O(n)性能的桶排序,我们需要保证排序每个桶所花费的总时间为O(n)。我们定义ni是分到桶bi的元素数目。我们能够将ni看做随机变(使用统计理论)。现在考虑ni的期望值E[ni]。输入中的每一个元素插入到一个给定的桶中的概率为1/p,因为每个元素的值是从[0,1)之间均匀抽取的。因此E[ni]=n*p=n*(1/n)=1,方差Var[ni]=n*p*(1-p)=(1-1/n)。考虑方差是非常重要的,因此有些桶可能是空的,而其他的可能有多于一个元素;我们需要保证没有桶包含过多的元素。我们再一次通过统计理论得到下面的等式:

从这个等式我们能够计算出ni2的期望值。这个计算是非常关键的,因为这是决定插入排序开销的关键因素,插入排序的最坏情况性能为O(n2)。我们计算出E[ni2]=(1-1/n)+1=(2-1/n),可以看到E[ni2]是一个常数。这个意味着当我们将在n个桶上执行插入排序的总开销加起来之后,总的期望性能为O(n)。