一个排序算法的平均时间复杂度

Question

我有一个treesort函数，它执行两个不同的任务，并具有各自的时间复杂度。我已经计算出了这两个任务的平均情况时间复杂度，但如何找到算法的总体复杂度？

例如，该算法接受一个随机列表的“n”个键x：

Sort(x):
    Insert(x):
        #Time complexity of O(nLog(n))
    Traverse(x):
        #Time complexity of O(n)

我只需要将这两个复杂度相加得出O(n + nLog(n))，还是要选择主要的任务（在这种情况下是插入），最终得到O(nLog(n))的总体复杂度呢？

- tvguide1234

Answer 1

在像这样简单的情况下，

O((n) + (n log(n)) = O(n + n log(n))
                  = O(n (log(n) + 1))
                  = O(n log(n))

- Pointy

Answer 2

或者我承担主导任务（在这种情况下是插入），最终得到O(nLog(n))的过度复杂性
没错。随着n的增长，O(n + nLog(n))总和中的第一个元素将变得越来越不重要。因此，对于足够大的n，它的贡献可以忽略不计。

- Nikita Rybak

Answer 3

你需要选择主导因素。

这种衡量复杂度的方法的整个思想是基于假设，即你想知道在大的 n 下会发生什么。

所以如果你有一个多项式，你可以舍弃除最高次元素外的所有元素，如果你有一个对数，你可以忽略底数等等。

然而，在日常实践中，这些差异可能开始变得重要，因此有时候有一个更精确的算法复杂度的图片是很好的，甚至到你赋予不同操作不同权重的级别。

(回到你最初的问题，假设你使用的是以 2 为底的对数，在 n=1048576 时，n+n*logn 和 n*logn 之间的差异约为 5%，这可能并不值得担心。)

- biziclop