两个不嵌套的for循环的大O符号表示是什么?
示例:
for(int i=0; i<n; i++){
System.out.println(i);
}
for(int j=0; j<n; j++){
System.out.println(j);
}
两个不嵌套的for循环的大O符号表示是什么?
示例:
for(int i=0; i<n; i++){
System.out.println(i);
}
for(int j=0; j<n; j++){
System.out.println(j);
}
线性的
O(n) + O(n) = 2*O(n) = O(n)
无论您有多少个非嵌套循环(如果这个数量是一个常数且不取决于n
),复杂度都将是线性的,并且等于循环中的最大迭代次数。
O(n ^ 2)
时,您应将它们拆分为两个单独的循环以获得以一些内存为代价的O(n)
? - ACVm
次,而第二个循环迭代了 n
次,其中 n>>m
。 - santobedim
不是 n
的函数,那么它就无关紧要。 - Salvador DaliO(n)
还是O(m+n)
还是O(m)*O(n)
?其中m
和n
是独立的,m
不是n
的函数。 - santobediO(max(m,n))
- Salvador Dali从技术上讲,这个算法仍然在O(n)时间内运行。
虽然迭代次数每增加1个 n
,就会增加2个,但是花费的时间仍然以线性速率增加,因此,它仍然是O(n)时间复杂度。
由于你运行n+n=2n次迭代,因此它将是O(2n)。
O(2n)基本上相当于O(n),因为2是一个常数。
这段话涉及到it技术,意思是“O(n) + O(n) ==> 实际上是O(n), 因为我们不保留常数值。” 。