O（N + M）时间复杂度 [英] O(N+M) time complexity

问题描述

我正在解决一些练习问题，在这些问题中，我确定了目标时间复杂度和空间复杂度。其中之一给出目标时间复杂度为O（N + M）。我对O（N + M）算法的外观有些直觉。是否有人有这样的算法示例，或者可以清楚地解释它？我尝试想到的每个示例对我来说似乎都是O（N * M）。

I'm working through some practice problems where I'm given a target time complexity and space complexity. One of them gives a target time complexity of O(N+M). I'm having some trouble with the intuition of what an O(N+M) algorithm would look like. Does anyone have an example of an algorithm like this or can explain it clearly? Every example I try to think of seems like O(N*M) to me.

推荐答案

一个简单的算法示例 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;
}

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

To compute the sum, you need to go through all elements in nArr (size n) and all elements in mArr (size m), so the overall complexity is O(m+n)

这篇关于O（N + M）时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！