两个非嵌套循环的Big O表示法

Question

两个不嵌套的for循环的大O符号表示是什么？

示例：

for(int i=0; i<n; i++){
   System.out.println(i);
}

for(int j=0; j<n; j++){
   System.out.println(j);
}

- idude

---

可能是Big O的简明英语解释的重复问题。 - GayashanNA

Answer 1

线性的

O(n) + O(n) = 2*O(n) = O(n)

无论您有多少个非嵌套循环（如果这个数量是一个常数且不取决于n），复杂度都将是线性的，并且等于循环中的最大迭代次数。

- Salvador Dali

---

这是否意味着，当您有两个嵌套循环O（n ^ 2）时，您应将它们拆分为两个单独的循环以获得以一些内存为代价的O（n）？ - ACV

如果两个循环的迭代次数不同会发生什么？例如，第一个循环迭代了 m 次，而第二个循环迭代了 n 次，其中 n>>m。 - santobedi

如果 m 不是 n 的函数，那么它就无关紧要。 - Salvador Dali

@SalvadorDali 在我的情况下时间复杂度会是什么？O(n)还是O(m+n)还是O(m)*O(n)？其中m和n是独立的，m不是n的函数。 - santobedi

@santobedi O(max(m,n)) - Salvador Dali

Answer 2

从技术上讲，这个算法仍然在O(n)时间内运行。

虽然迭代次数每增加1个 n，就会增加2个，但是花费的时间仍然以线性速率增加，因此，它仍然是O(n)时间复杂度。

- Luke Joshua Park

Answer 3

由于你运行n+n=2n次迭代，因此它将是O(2n)。

O(2n)基本上相当于O(n)，因为2是一个常数。

- Atri

Answer 4

这段话涉及到it技术，意思是“O(n) + O(n) ==> 实际上是O(n), 因为我们不保留常数值。” 。

- TheLostMind

Answer 5

假设每个循环都运行到n，因此我们可以说每个for循环的复杂度为O(n)，因为每个循环将运行n次。对于第一个循环O(n)+第二个循环O(n)+第三个循环O(n)的线性情况，我们可以说它们没有嵌套，这将给你3O(n)。现在，由于我们大多数集中在复杂度的可变部分上，我们将排除常量部分，并表示这种情况是O(n)。但在实际情况中，我建议您记住常量因素也会起到至关重要的作用，因此永远不要忽略它们。例如，考虑查找整数数组中最小整数的时间复杂度，任何人都会说它是O(n)，但查找相同数组的第二个最大或最小值将是O(2n)。但大多数答案将说它是O(n)，实际上忽略了常量。考虑如果数组大小为1000万，则该常量不能被忽略。

- Palash Rathore