Сложность алгоритма сортировки

Question

У меня есть функция treeort, которая выполняет две различные задачи, каждая со своей собственной временной сложностью. Я понял, avg. временную сложность двух задач, но как найти общую сложность алгоритма.

Например, алгоритм принимает в случайном списке «п» ключи х:

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

ли я просто добавить две сложности вместе, чтобы дать мне O (п + NLog (п)) или я (в данном случае Вставка) и в конечном итоге с общей сложностью O (nLog (n))

Answer 1

или я занимаю доминирующую задачу (в этом случае Вставка) и заканчивается сложностью of O (nLog (n))
Правильно. Поскольку n растет, первый элемент в O(n + nLog(n)) сумма станет менее значимой. Таким образом, при достаточно большом n его вклад можно игнорировать.

Answer 2

Вам нужно взять доминирующий.

Вся идея измерения сложности таким образом основана на предположении, что вы хотите знать, что происходит с большими n.

Итак, если у вас есть многочлен, вы можете отбросить все элементы, кроме самого высокого порядка, если у вас есть логарифм, вы можете игнорировать базу и так далее.

В повседневной практике эти различия могут начать иметь значение, поэтому иногда бывает полезно иметь более точную картину сложности вашего алгоритма, вплоть до уровня, на котором вы назначаете разные веса для разных операций.

(Возвращаясь к исходным вопросам, предполагая, что вы используете базовые 2 логарифмов, в n=1048576, разница между n+n*logn и n*logn составляет около 5%, что, вероятно, на самом деле не стоит беспокоиться.)

Answer 3

В простой случай, подобный этому,

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