难以理解为什么两个嵌套循环的复杂度为O（n）？

Question

因此，在以下代码中，j执行n时间when i = 0。一旦i迭代一次(i = 0,2,3....n)，就j永远不会执行，因为if语句的条件为true并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。因为你增加j的nif语句中，这相当于调用break;，从而退出for循环的最里面的一个迭代后。

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

• 迭代到nwhen i == 0。
• 当时i > 0，它仅迭代一次。

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