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

Question

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

Например, алгоритм принимает в случайном списке «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))

Answer 2

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

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

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

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

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

Answer 3

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