java - 难以理解为什么两个嵌套循环的复杂度为 O(n)？

Question

所以在下面的代码中，当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?

Answer 1

最里面的条件，if (j < i) , 在 i >= 1 时始终为真, 作为 j初始化为 0 .因为你递增 j通过 n在 if 语句中，这相当于调用 break; ，从而在单次迭代后退出最内层的 for 循环。

所以回答你的问题，时间复杂度是O(n)因为最里面的 for 循环只会迭代 2n - 1次:

• 迭代到n什么时候i == 0 .
• 何时i > 0 , 它只迭代一次。

感谢Phoenix1355在下面的评论中指出这一点。