同步阅读进度,多语言翻译,过滤屏幕蓝光,评论分享,更多完整功能,更好读书体验,试试 阅读 ‧ 电子书库
分析
在例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)。
请支持我们,让我们可以支付服务器费用。
使用微信支付打赏