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

Question

我有一个treeort函数,它执行两个不同的任务,每个任务都有自己的时间复杂度.我想出了平均值.两个任务的案例时间复杂度,但我如何找到算法的整体复杂性.

例如,算法接收"n"个键x的随机列表:

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

我只是将两个复杂性加在一起给我O(n + nLog(n))或者我是否采取主导任务(在本例中为Insert)并最终得到总体复杂度为O(nLog(n))

Answer 1

在这种简单的情况下,

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