time-complexity - sort(..) 如何影响我算法的 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)？

标签： time-complexitybig-o

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

您不能因为将代码块隐藏在函数调用后面并假设它是O(1)因为“它只是一个函数调用”而忽略了代码块的复杂性。您必须计算复杂性，就好像您将在该位置复制并粘贴该函数的代码一样。