首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >Bucket排序的运行时间

Bucket排序的运行时间
EN

Stack Overflow用户
提问于 2015-11-18 19:59:12
回答 1查看 320关注 0票数 0

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

EN

回答 1

Stack Overflow用户

发布于 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
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/33779500

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档