Как сортировка (..) влияет на нотацию Big-O моего алгоритма

Question

Если мой алгоритм имеет сложность O(n), но я использую алгоритм сортировки внутри, который имеет O(n log n), нужно ли мне их считать?

def function(array A):
    A.sort()
    for i in A:
         ...

Будет ли это теперь официально O(n) или O(n log n)?

Answer 1

Общая сложность зависит от сложности A.sort().

• Когда сложность A.sort() равна O(1) (что, скорее всего, нет), то сложность вашей функцииравен O(n) (в зависимости от содержимого цикла for).
• Если сложность A.sort() равна O(n) (что может быть, но обычно нет), тогда сложность вашей функциипо-прежнему O(n), поскольку это будет O(2*n).
• Если сложность A.sort() равна O(n log n), то сложность вашей функции равна O(n log n), а цикл for равенпо сравнению с этим можно пренебречьвызов функции ". Вы должны вычислить со сложностью, как если бы вы скопировали и вставили код этой функции в этом месте.