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

Question

对于没有嵌套的循环,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(n) + O(n) = 2*O(n) = O(n)

无论你有多少非嵌套循环(如果这个数字是常数而不依赖n),复杂性将是线性的,并且等于循环中的最大迭代次数.

Answer 2

从技术上讲,该算法仍在O(n)时间内运行.

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

Answer 3

其复杂度为 O(2n)，因为您运行了 n+n = 2n 次迭代。

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