这段代码的复杂度是多少？我们应该总结复杂性吗？

Question

我有一个算法，首先对向量进行排序，然后遍历其元素和 XOR 它们。我是否应该将 sort 和 for 循环的复杂性相加来计算整个算法的复杂性？所以，我有下一个代码：

std::sort(array.begin(), array.end());
for (int i =1; i < array.size(); ++i) {
  result = array[i-1]^array[i];
}

我们有一个 for 循环，它有 O(N) 复杂度和 std::sort 平均有 O(N log N) 次比较。那么下一段代码的复杂度会是O(N + N log N)？或者在这种情况下，我们只需要选择最高时间复杂度 class，即线性时间 O(N log N) 并且不对它们求和？

Answer 1

复杂度 class O(N) 是 class O(N log N) 的子集，因为 log N > 1 足够高 N。因此，代码 O(N + N log N) 的复杂度 class 是 O(2 N log N) 的子集，并且由于复杂度 class 是不变的 w.r.t。常量，最后是O(N log N)。

Answer 2

我们计算复杂度的方法是在所有复杂度中选择最高的。

所以，假设您有以下代码

for i in range 0 to n
{
    for  in range 0 to n
    {
        \ code
    }
}

for i in range 0 to n
{
    \ code
}

所以，这里的复杂性是 O(n^2) + O(n)。最终将是 O(n^2)。所以，上面整个代码的复杂度是O(n^2).

同样，在您的情况下，复杂度为 O(N log N) + O(N)，这使得最终复杂度为 O(N log N)

Answer 3

运行时间受排序步骤限制，O(nlgn)。 for循环可能有O(n)的复杂度，但整体的运行时间总是以最高幂为主。请在此处查看数学证明：

https://math.stackexchange.com/questions/324200/big-o-notation-sum-rule

Answer 4

是的，您可以将它们相加：O(n) 和 O(n log n) 变为 O(n + n log n)。但请注意，这是 而不是 O(2n log n)，因为在基本算术中，加法在乘法之后。

现在，就像 O(1 + n) 总是减少到 O(n) 一样，您的 O(n + n log n) 将减少到 O(n log n)，因为单独的 n 项更少比 n log n 项，大 O 表示法总是关于极限，而不是精确的方程。

有些人可能会发现从一开始就认识到 O(n) 被 O(n log n) 支配更直观，并且从不首先对它们求和。这是一个有用的思维捷径，但两种观点都会得到相同的结果。

Answer 5

首先，O(N+N log N)不会给你O(2N log N)，它会给你O( (log N+1) * N)。该算法将受到 O(N log N) 的限制，因为随着 N 接近无穷大，它的增长速度快于 O(N)。

这段代码的复杂度是多少？我们应该总结复杂性吗？

What will be the complexity of this code? Should we sum complexities?

c++

sorting

algorithm

time-complexity

asymptotic-complexity