O(nlogn) + O(n)的时间复杂度是否仅为O(nlogn)？
O(nlogn) + O(n)的时间复杂度是否仅为O(nlogn)？
提问于 2018-09-13 07:55:37
假设我有一个长度为n的数组，我使用带有time nlogn的排序算法对它进行了排序。得到这个排序后的数组后，我遍历它以查找任何具有线性时间的重复元素。我的理解是，由于操作是分开进行的，所以应该是time O(nlogn) + O(n)而不是O(nlogn+n)。如果是这样的话，nlogn是否会取代线性时间复杂度，使最终的时间复杂度为O(nlogn)
回答 1
Stack Overflow用户
发布于 2018-09-13 08:03:26
对大的n，由于log(n) >1，所以O(nlog(n))是O(n)的超集。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/52304886
复制相关文章
相似问题