所以在下面的代码中,当i = 0
时,j
执行了n
次。只要 i 迭代一次 (i = 0,2,3....n)
,j
就不会执行,因为 if 语句的条件为真且 n
被添加到 j
。 i
继续迭代直到 n
,这是循环(两个循环)停止执行并且方法结束的时候。
public static void main(String[] args) {
int x = 0;
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
if(j < i) j = j + n;
else x = x+1;
}
}
}
我的困惑在于,为什么时间复杂度是O(n)
,当两个循环在某个时刻迭代到n
时,i
总是迭代to n
and j
迭代到 n
when i = 0
... 应该不是O (n^2)
因为我们乘以 nxn
?
最佳答案
最里面的条件,if (j < i)
, 在 i >= 1
时始终为真, 作为 j
初始化为 0
.因为你递增 j
通过 n
在 if 语句中,这相当于调用 break;
,从而在单次迭代后退出最内层的 for 循环。
所以回答你的问题,时间复杂度是O(n)
因为最里面的 for 循环只会迭代 2n - 1
次:
- 迭代到
n
什么时候i == 0
. - 何时
i > 0
, 它只迭代一次。
感谢Phoenix1355在下面的评论中指出这一点。
关于java - 难以理解为什么两个嵌套循环的复杂度为 O(n)?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/55859546/