看算法导论桶排序那一节的时候有这么一句话
只要所有桶的尺寸的平方和与总的元素数呈线性关系, 那么桶排序也可以在O(N)完成
我想问的是, 当输入的元素不满足均匀分布时, 怎么能固定桶的大小呢?如果固定了桶内元素的个数,就有可能出现一个桶元素放满之后放不下溢出的问题, 那么这句话该怎么理解呢?
看算法导论桶排序那一节的时候有这么一句话
只要所有桶的尺寸的平方和与总的元素数呈线性关系, 那么桶排序也可以在O(N)完成
我想问的是, 当输入的元素不满足均匀分布时, 怎么能固定桶的大小呢?如果固定了桶内元素的个数,就有可能出现一个桶元素放满之后放不下溢出的问题, 那么这句话该怎么理解呢?