关于两个依赖嵌套循环时间复杂度的计算困惑

嘿，我完全懂你现在的纠结点——你不小心把循环的执行逻辑算错啦！让我一步步给你理清楚：

首先，先明确你说的这类嵌套循环的典型结构，大概是这样的（用伪代码举例）：

for i from 0 to N-1:
    for j from i+1 to N-1:
        # 执行某些O(1)操作

你的错误在于：把外层循环的迭代次数和内层循环的「单次最大迭代次数」相乘了，但实际上内层循环的迭代次数是随着外层的i变化而递减的，并不是每次都跑接近N次。

我们来实打实算总执行次数：

• 当i=0时，内层循环j从1到N-1，一共跑N-1次
• 当i=1时，内层循环j从2到N-1，一共跑N-2次
• ...
• 当i=N-2时，内层循环j从N-1到N-1，一共跑1次
• 当i=N-1时，内层循环根本不会执行，跑0次

把这些次数加起来，总和就是：1 + 2 + ... + (N-1)，这个等差数列的求和结果是N(N-1)/2。

现在看这个式子的最高次项——是N²，而时间复杂度只看最高次项（忽略系数和低次项），所以最终的时间复杂度是O(N²)，和教材说的一致。

举个小例子验证下：假设N=4，总执行次数是3+2+1=6次，而4*3/2=6，对应的最高次是4²=16的量级，显然是O(N²)，完全和O(N³)不沾边~

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