无法理解为什么两个嵌套循环的复杂性为O（n）？

Question

所以在下面的代码中，当j时，n执行i = 0次。一旦我迭代一次(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总是迭代到n而j迭代到n当i = 0 ...它不应该是O(n^2)因为我们乘以nxn？

Answer 1

当if (j < i)被i >= 1初始化为j时，最里面的条件0总是正确的。因为你在if语句中用j增加n，这相当于调用break;，因此在单次迭代后退出最里面的for循环。

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

• 它在n时迭代到i == 0。
• 当i > 0时，它只迭代一次。

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

Answer 2

您还可以通过传递不同的输入（n）来分析时间复杂度。我复制了相同的代码并创建了一个单独的函数：

private static void testComplexity(int n) {
    int x = 0;
    int N1 = 0, N2 = 0;
    for (int i = 0; i < n; i++) {
            N1++;
        for (int j = 0; j < n; j++) {
                N2++;
            if(j < i) j = j + n;
            else x = x+1;
        }
    }
    System.out.println("input is : " + n + " and N1 " + N1 + " and N2 : " + N2);
}

public static void main(String[] args) {
    int[] inputs = new int[]{10, 100, 1000, 10000};
    for(int input : inputs) testComplexity(input);
}

输出是：

输入为：10和N1：10和N2：19 输入为：100和N1：100和N2：199 输入为：1000和N1：1000和N2：1999 输入为：10000和N1：10000和N2：19999

我为QUADRATIC创建了另一个函数

    private static void testComplexity2(int n) {
    int N1 = 0, N2 = 0;
    for (int i = 0; i < n; i++) {
            N1++;
        for (int j = 0; j < n; j++) {
                N2++;
        }
    }
    System.out.println("input is : " + n + " and N1 " + N1 + " and N2 : " + N2);
}

输出是：

输入为：10和N1 10和N2：100 输入为：100和N1 100和N2：10000 输入为：1000和N1 1000和N2：1000000 输入为：10000和N1 10000和N2：100000000

你觉得区别吗？