关于三重嵌套循环时间复杂度的疑问：O(n²)还是O(n³)？

首先，咱们先把时间复杂度的核心逻辑理清楚：它只关心总执行次数的最高阶项，常数、低次项都可以忽略，所以不用纠结具体数值，看数量级就行。

一步步推导你的情况： #

1. 先看i和j的循环：你说这部分符合高斯求和，也就是总次数是1+2+...+n = n(n+1)/2，这确实是O(n²)，没毛病。
2. 再看第三层k循环：关键是它每次执行多少次，以及所有k循环的总累加次数。你测试n=7得到count=35，咱们来对比数量级：
   • 如果是O(n³)，n=7时n³=343，35和343差了一个数量级，完全不沾边；
   • 如果是O(n²)，n=7时n²=49，35和49属于同一数量级（都是几十），完全符合O(n²)的特征。

那为什么是三重循环却还是O(n²)？很简单——第三层循环的总累加次数没达到n³的量级。举个例子：

• 如果k循环每次只执行1次，总次数就是n(n+1)/2=28（n=7时），和你的35很接近；
• 就算k循环偶尔执行多次，但整体累加下来，最高次项还是n²，那时间复杂度就还是O(n²)。

验证小技巧： #

你可以再测个n=10：

• 如果count在50-60左右（比如10*11/2=55），那肯定是O(n²)；
• 如果count接近1000，那才是O(n³)。

要是能把循环的代码贴出来，咱们能更精准地计算，但目前根据你的测试结果，基本可以确定你的算法时间复杂度是O(n²)，不是O(n³)。

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