请求确认给定嵌套循环的Big O时间复杂度

嘿，你的初步判断完全正确！咱们来一步步拆解这个循环，把复杂度的推导过程理清楚，这样你就能彻底明白为什么它是O(n²)了。

首先先把你的循环代码明确写出来：

for(i=0; i<n; i++) {
    for(j=0; j<n-i; j++) {
        print(i);
    }
}

接下来咱们计算这个循环的总执行次数：

• 当i=0时，内层循环j从0到n-1，总共执行n次
• 当i=1时，内层循环j从0到n-2，总共执行n-1次
• 当i=2时，内层循环执行n-2次
• ...
• 当i=n-1时，内层循环只执行1次

把这些次数加起来，就是一个等差数列求和：

总次数 = n + (n-1) + (n-2) + ... + 2 + 1

等差数列的求和公式是n*(n+1)/2，展开后就是(n² + n)/2，也就是(1/2)n² + (1/2)n。

现在来看Big O复杂度的规则：我们只保留主导项（也就是增长最快的项），并且忽略项前面的常数系数。这里(1/2)n²是主导项，(1/2)n是低阶项，常数系数1/2也可以忽略，所以最终的时间复杂度就是O(n²)。

简单来说，虽然内层循环的次数随着i增加在减少，但整体的执行次数还是和n的平方成正比，所以你的初步判断完全准确。

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