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

Question

对于两个未嵌套的 for 循环，Big O 表示法是什么？

示例：

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

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

Answer 1

这将是 O(2n) 因为你运行 n+n = 2n 次迭代。

O(2n) 本质上等同于 O(n)，因为 2 是常数。

Answer 2

线性

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

你有多少个非嵌套循环并不重要（如果这个数字是一个常数并且不依赖于n）复杂度将是线性的并且等于循环。

Answer 3

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

虽然n每次增加迭代次数增加2次，但所花费的时间仍然以线性的速度增加，因此，O(n)时间.

Answer 4

它将是 O(n) + O(n) ==> 实际上 O(n) 因为我们不保持常量值。

Answer 5

假设一个场景每个循环运行s 最多 n

所以我们可以说每个 for 循环的复杂度是 O(n) 因为每个循环将运行 n 次。

所以你指定这些循环不嵌套在线性场景中 第一个循环 O(n)+ 第二个循环 O(n)+ 第三个循环 O(n) 这将给你3O(n).

现在，由于我们主要关注复杂性的可变部分，因此我们将排除常量部分，并称在这种情况下它是 O(n)。

但在实际场景中，我建议您记住，常数因子也将起着至关重要的作用，因此永远不要排除它们。

例如，考虑从整数数组中找到最小整数的时间复杂度，任何人都会说它是 O(n)，但要找到同一数组的第二大或最小整数将是 O(2n)。

但大多数答案会说 O(n) 实际上忽略了常量。考虑如果数组的大小为 1000 万，那么该常数不能被忽略。

Big O Notation for two non-nested loops