只要所有桶的尺寸的平方和与总的元素数呈线性关系, 那么桶排序也可以在O(N)完成
看算法导论桶排序那一节的时候有这么一句话
只要所有桶的尺寸的平方和与总的元素数呈线性关系, 那么桶排序也可以在O(N)完成
我想问的是, 当输入的元素不满足均匀分布时, 怎么能固定桶的大小呢?如果固定了桶内元素的个数,就有可能出现一个桶元素放满之后放不下溢出的问题, 那么这句话该怎么理解呢?
如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。
绑定邮箱获取回复消息
由于您还没有绑定你的真实邮箱，如果其他用户或者作者回复了您的评论，将不能在第一时间通知您！
发布评论
评论（1）
这里桶的大小没有要求固定，而只是要求“桶的尺寸的平方和与总的元素数呈线性关系”。这个关系是在big-O下要求成立的，可以理解成极限或者期望情况下，桶的尺寸的平方和满足线性关系即可。