时间复杂度如何影响程序实际执行时间？附O(n³)三重循环实测案例

时间复杂度与实际运行时间的关系 #

大O时间复杂度描述的是输入规模足够大时，程序运行时间随规模增长的渐近趋势，它会忽略三类成本：固定开销、常数系数、低阶运算项，只保留最高阶的增长规律。你这段代码的核心逻辑是三层嵌套循环，每层循环执行n次，循环总次数为n³，因此时间复杂度为O(n³)，也就是说当n足够大、固定开销占比可以忽略时，运行时间和n的三次方成正比。

观测到的耗时差异原因 #

我们先拆解两次测试的核心参数：

• temp=10时，循环总次数为 10*10*10 = 1000 次，总耗时50ms
• temp=100时，循环总次数为 100*100*100 = 1000000 次，总耗时~3000ms

循环次数差了1000倍，但总耗时只涨了60倍，核心原因是小输入规模下固定开销占比极高，稀释了O(n³)的增长趋势，你的程序耗时可以拆成两部分：

• 固定开销：JVM启动、类加载、时间函数调用、输出流初始化的成本，这部分和输入规模无关，不管temp是10还是100，这部分成本基本固定，大概在45~48ms左右，占了temp=10时总耗时的90%以上
• 可变开销：循环执行、字符串拼接、System.out.println 输出的成本，这部分和循环次数正相关，也就是和n³成正比

我们可以简单做个计算：设固定开销为a，单次循环的平均可变开销为b，代入你的测试数据可得：

a + 1000b = 50
a + 1000000b = 3000

计算可得b≈0.003ms/次，a≈47ms，完全符合实际观测的结果。

除此之外还有两个细节会进一步缩小耗时涨幅：

1. System.out.println 是带缓冲的IO操作，小批量输出时缓冲刷新的额外开销占比高，大批量输出时会批量刷新缓冲，单次打印的平均成本更低
2. JVM的JIT即时编译会在代码执行足够多次后将热点代码编译成本地机器码，temp=10时循环次数太少，代码还处于解释执行阶段，temp=100时循环次数足够多，JIT优化生效，执行效率更高

如果你把temp分别调到20、30、50测试，扣除固定的~47ms开销后，剩下的可变耗时会和temp的三次方成严格正比，完全匹配O(n³)的时间复杂度规律。

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