假设我有一个长度为n
的数组,我使用带有time nlogn
的排序算法对它进行了排序。得到这个排序后的数组后,我遍历它以查找任何具有线性时间的重复元素。我的理解是,由于操作是分开进行的,所以应该是time O(nlogn) + O(n)
而不是O(nlogn+n)
。如果是这样的话,nlogn
是否会取代线性时间复杂度,使最终的时间复杂度为O(nlogn)
发布于 2018-09-13 08:03:26
对大的n,由于log(n) >1,所以O(nlog(n))是O(n)的超集。
https://stackoverflow.com/questions/52304886
复制相似问题