O(N+M)时间复杂度

Question

我正在解决一些练习问题，这些问题要求我给出目标时间复杂度和空间复杂度。其中一个目标时间复杂度为O(N+M)。我对O(N+M)算法的直观理解有些困难。有没有人能举个例子或清晰地解释一下？我尝试想到的每个示例似乎都像O(N*M)。

- user137717

---

你能否提供一个O(N+M)的案例示例？ - Javi

是的，这样我们就可以找出特定情况下N和M的值。我现在能想到的是：找到两个向量中的最小值，一个大小为N，另一个大小为M，这样时间复杂度将为O(M+N)。 - Javi

如果可以的话，我想避免它。下面的答案是一个很好的例子，我不想发布问题，因为担心有人会透露太多答案。谢谢你的帮助！ - user137717

如果您需要正式的定义，请参考：http://en.wikipedia.org/wiki/Big_O_notation#Multiple_variables - Tavian Barnes

Answer 1

一个简单的算法示例，其时间复杂度为O(m+n):

int sum(int[] nArr, int[] mArr) {
    int sum = 0;
    for(int i : nArr) {
        sum += i;
    }
    for(int i : mArr) {
        sum += i;
    }
    return sum;
}

为了计算总和，您需要遍历nArr（大小为n）中的所有元素和mArr（大小为m）中的所有元素，因此总体复杂度为O(m+n)。

- Jean Logeart

---

从复杂度的角度来看，这是不可能做得更好的 :) - Jean Logeart

假设大小为N的数组nArr更大。说这个算法是O(N)仍然正确吗？ - user137717

不，这是不正确的，除非“m”是常数或者“m”取决于“n”，使得“m = O(n)”。 - Jean Logeart

把它看作是一个O(n)算法后跟一个O(m)算法，它们一起是O(n+m)，并将其抽象到任意数量的数组中，这样想是否正确？ - user137717

复杂度注释(例如 O)描述了算法的性能(例如时间或空间)如何取决于输入的大小，它是“盲目”的，不针对特定的输入。当你写 O(m+n) 时，这意味着当m > n时，该算法将花费 O(m) 时间，而当m < n时，则需要 O(n) 时间。无论如何，O(m+n) = O(max(m,n))。 - Shaked

Answer 2

一个O(n + m)算法的快速简单示例:

for (i = 0; i < n; i++)
{
  // do something but don't loop or invoke recursive functions
  // only constant O(c) complexity is allowed: a simple series of commands
}

for (i = 0; i < m; i++)
{
  // idem
}

当增加时，复杂度是可交换的 (O(n + m) == O(m + n))，这意味着您可以反转两个for()而不影响复杂度。显然，在算法级别上，反转后的循环可能与直接的循环并不等价。

作为额外的帮助，这里有一个O(n * m)算法的例子：

for (i = 0; i < n; i++)
{
  for (j = 0; j < m; j++)
  {
    // do something but don't loop or invoke recursive functions
    // only constant O(c) complexity is allowed: a simple series of commands
  }
}

再次强调，您可以在内部和外部循环之间反转而不影响复杂度（O(n * m) == O(m * n)）。同样的显而易见的考虑也适用。

对于您可能放入for()体中的内容的限制是因为大O符号约束了上界。如果它是一个下界（小o符号），您可以放入更复杂的内容，但它永远不能低于那个。

- pid

Answer 3

这个问题的直觉是你有两个唯一的变量n和m。现在想象这两个唯一的变量独立增加，趋近于无限大。

如果这是一个O(n)问题（即BIG-O），那么这个问题的复杂度上限至少是线性的。你可以说O(n)=n^2。但是，当输入n趋近于无穷大时，O(n)问题甚至不会接近于n^2的限制。

同样，对于m的行为也是相同的。O(m)可以是m^2。但更准确地说，O(m)=m。这两个问题的复杂性都是线性的。

现在，如果你只做O(n+m)，那真的是n^2吗？不应该是的。即使n=m，总和也将是2n或2m。这个问题的复杂度仍然是线性的，因为输出的大小仍然与输入n和m成比例。因此，这个问题的最精确的答案应该是O(n+m)=n+m。

- Caleb Faruki

Answer 4

因此，为了扩展其他答案，我将尝试添加一个示例来帮助您理解此类问题：

• 在大小为N的数组中查找最小/最大值，然后在大小为M的数组中查找该值。由于您需要先执行最小/最大搜索，因此无法一次完成。

例如，对两个向量的元素求和可以在O（M+N）内完成，但可以认为它是O（N）（假设N＞M）或O（M）（如果M＞N）。

- Javi

---

假设N<M，则其为O(M)，因此O(M+N)仅为max(O(M), O(N))，仍然是线性的。 - Mephy

嗯，我觉得这是显而易见的。不过，我已经更新了答案。无论问题是什么，O(M+N)都是线性的。 - Javi

Answer 5

所有上面的答案都说明了O(n+m)是如何工作的，但我想从不同的角度来看它，了解一下O(nm)是什么，O(n+m)和O(nm)之间的区别在于，当将一个n数乘以m数时，这意味着n将发生m次或尝试m次，例如，下面的代码是O(n*m)，因为n将在n次中发生m次。

for(int i=0; i < n;i++){
  for(int j=0; j < m;j++){
  //some_code
  }
}

- m.mashaly

---

这个答案不已经涵盖了吗？链接 - kaya3

抱歉，我没看到它。 - m.mashaly

Answer 6

一个非常有启示性的例子是将两个大小为M和N的已排序数组合并成一个新的排序数组。这就是归并排序的基础，需要进行O(M+N)次比较。

您可以在任何地方找到一个例子或自己尝试实现。

- user1952500