开发者社区

文档建议反馈控制台

文章/答案/技术大牛

发布

社区首页 >问答首页 >为什么合并排序时间复杂度不是O(N)？

问为什么合并排序时间复杂度不是O(N)？
EN

Stack Overflow用户

提问于 2015-03-25 04:29:53

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

归并排序的时间复杂度为O(n log n)，因此n在logn上占主导地位，归并排序的时间复杂度为O(N)

谢谢

EN

回答 1

Stack Overflow用户

发布于 2015-03-25 04:33:31

使用传统的排序算法，O(n log n)是最好的。

你不能说O(n log n) == O(n)，即使n主宰了logn，因为它们是乘法，而不是加法。

如果你得到n + logn并且n支配logn，那么你可以说O是O(n)

票数 0

EN

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

原文链接：

https://stackoverflow.com/questions/29242287

复制

相似问题