嵌套循环时间复杂度咨询：无效内循环、双变量内循环及三层嵌套循环时间复杂度分析

嘿，咱们逐个拆解这些问题，这些例子刚好能帮你搞清楚循环条件和变量怎么影响大O复杂度分析！

问题1：内循环条件恒不成立时，时间复杂度是O(n)吗？ #

先看你给的示例代码：

for (int i=0; i<n; i++){ 
    for (int j=0; j>n; i++){ 
        //some code 
    } 
}

答案是是的，时间复杂度为O(n)。原因很简单：

• 外循环会完整执行n次（每次做i的初始化、条件判断、自增这些固定操作）。
• 内循环的条件j>n从一开始就不成立（j初始是0，而我们分析时间复杂度时默认n是代表输入规模的正整数），所以内循环一次都不会进入循环体，每次外循环里内循环的开销只是常数级的条件判断。
• 总操作次数就是n乘以常数级操作，所以复杂度是O(n)。

问题2：内循环用另一个变量m作为条件，时间复杂度是O(nm)吗？ #

看你的示例代码：

for (int i=0; i<n; i++){ 
    for (int j=0; j<m; i++){ 
        //some code 
    } 
}

先提个小细节：你代码里内循环的自增写的是i++，这应该是笔误吧？正常应该是j++，不然逻辑会出问题（比如i被内循环疯狂自增，外循环直接跳完甚至无限循环），我就按正确的j++来分析啦。

如果是j++的话，答案是是的，时间复杂度为O(nm)：

• 外循环执行n次，每一次外循环里，内循环会完整执行m次（因为j从0到m-1，每次自增1）。
• 总操作次数就是n*m次，这属于两个独立输入规模的乘积复杂度，常见于遍历二维数组（n行m列）这类场景。

要是真的是i++的错误写法，那这个代码逻辑有问题，没法用常规的大O分析，毕竟循环的执行次数完全失控了，所以咱们默认是笔误哈。

问题3：三重嵌套循环的运行时间分析 #

看这段代码：

for (int i = 0; i < n; i++) { 
    for (int j = 0; j > n; j++) { 
        for (int k = 0; k > n; k++) { 
            System.out.println("*"); 
        } 
    } 
}

咱们一步步拆：

1. 外循环（i循环）：i从0开始，每次自增1直到i≥n，所以会执行n次（n为正整数时）。
2. 中间循环（j循环）：每次进入外循环后，j初始化为0，然后判断j>n——这个条件从一开始就不成立（j=0，n≥1），所以中间循环一次都不会运行循环体，连最内层循环的门都没摸到。
3. 最内层循环（k循环）：因为中间循环根本没执行，所以这层循环完全不会被触发，System.out.println("*")一次都不会打印。

总开销就是外循环的n次固定操作，中间和内层的条件判断都是常数级且不执行循环体，所以时间复杂度是O(n)。

内容的提问来源于stack exchange，提问作者Anonymous