桶排序算法的运行时间 下式 的。每一个桶i有相同 的值
对i=0，1，…，n-1是成立
是不足为奇的，因为输入数组A中的每 一
个值都是等可能地落在任何桶内的。为了证 明上式，我们定义指示器随机变量 X
落在桶i中} 其中，i=0,1,…,n-1, j=1,2,…,n。于是，
组合：
桶排序算法的运行时间
项进行重新
(8.3 我们分别计算两个和式。指示器随机变量 1的概率为1/n，其他情况下为0.于是有
个期望值替换进式8.3，有 n(n
桶排序算法的运行时间 因此，桶排序的期望运行时间为Θ(n + n*O(21/n= Θ(n
为 将这两
因篇幅问题不能全部显示，请点此查看更多更全内容