文章/答案/技术大牛

发布

问Bucket排序的运行时间
EN

Stack Overflow用户

提问于 2015-11-18 19:59:12

回答 1查看 320关注 0票数 0

如果我们假设元素在给定的范围k内均匀分布，我们有10个桶。那么在对列表中的n个元素进行一次迭代之后，每个存储桶中的元素数量将是相同的。例如，我们使用快速排序对每个存储桶进行排序，但是我们知道每个存储桶中的元素数量是恒定的，那么总运行时间不是Θ(n)吗？

发布于 2015-11-18 22:45:37

不是的。

将元素放入10个桶中是O(N)。

使用qsort对一个存储桶进行排序的时间为O(NlogN) (实际上是N/10，但常量与复杂性无关)。

因此，总体复杂度将是O(N + 10 *N logN)，即O( NlogN ) (因为N

如果这很难理解，请尝试这样做:如果有2个存储桶而不是10个，那么您将对整个列表进行精确的Qsort。

票数 1

页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持

原文链接：

https://stackoverflow.com/questions/33779500

复制

相似问题

问Bucket排序的运行时间EN