algorithm - 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)