关于非常规嵌套for循环时间复杂度的确认咨询

嘿，你的猜测完全正确！咱们来一步步拆解这个嵌套循环，把这个结论彻底弄明白：

首先看内层循环的迭代次数，它和外层循环的i值直接相关：

• 当i=0时，j从n递减到1，总共执行n次
• 当i=1时，j从n递减到2，总共执行n-1次
• ...
• 当i=n-1时，j只能取n，总共执行1次

把这些次数加起来，就是一个从1到n的等差数列求和：
总执行次数 = n + (n-1) + (n-2) + ... + 1 = n(n+1)/2

现在算内层循环的平均迭代次数，就是总次数除以外层循环的n次：
平均次数 = [n(n+1)/2] / n = (n+1)/2

当n趋近于无穷大时，常数项1可以忽略不计，所以平均迭代次数确实约等于n/2，你的猜测完全没问题。

另外补充一下，这个嵌套循环的整体时间复杂度是O(n²)，因为n(n+1)/2的最高次项是n²/2，渐近复杂度只关注最高次项的量级，所以最终是O(n²)。

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