内层循环时间复杂度计算方法？Java嵌套循环复杂度分析疑问

首先明确：你提供的这段Java代码的时间复杂度是O(n²)。

代码执行次数拆解 #

先看你给出的代码：

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        System.out.println(j);
    }
}

• 外层循环：从i=1到i=n，一共执行n次，对应时间复杂度O(n)。
• 内层循环：每触发一次外层循环，内层循环就从j=1到j=n执行n次，单次内层循环的时间复杂度是O(n)。

总执行次数是外层循环次数 × 单次外层循环内的操作次数，也就是n × n = n²，对应时间复杂度O(n²)。

疑惑点解答 #

你误以为结果是O(n)*O(n²)，核心错误是对内层循环时间复杂度的误判：

• 内层循环本身的时间复杂度是O(n)，而非O(n²)。O(n²)是两层嵌套循环整体的时间复杂度，不是内层循环单独的复杂度。
• 正确的计算逻辑是：外层循环执行n次，每次执行一个O(n)的操作（即内层循环），所以整体复杂度是n × O(n) = O(n²)，而非用外层的O(n)去乘一个错误的内层O(n²)。

当n=10时，总执行次数为10×10=100，这完全匹配n²的计算结果，也验证了O(n²)的结论。

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