O(N + M)时间复杂度

Question

我正在解决一些实践问题,我给出了目标时间复杂度和空间复杂度.其中一个给出目标时间复杂度为O(N + M).我对O(N + M)算法看起来像什么的直觉有些麻烦.有没有人有像这样的算法的例子,或者可以清楚地解释它？我试图想到的每个例子对我来说都是O(N*M).

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)

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()身体的限制是因为big-o符号限制了上限.如果它是一个下限(小写符号)你可能会把更复杂的东西放进去,但它永远不会少于那个.