如何分析嵌套for循环的时间复杂度？附示例代码

先把待分析的代码贴出来：

Code(int n)
{
    int s=0; int i=0; int j=0;
    for(i < n; i++)
    {
        for(j = i; j < n; j++)
        {
            s += 1;
        }
    }
}

核心思路：统计最内层操作的总执行次数 #

时间复杂度推导的核心是看最内层重复执行的操作（这里是s += 1）一共运行多少次，其他辅助操作（变量声明、循环条件判断）要么是常数级，要么和内层操作的次数同阶，最终复杂度由最高阶项决定。

分步计算内层循环执行次数 #

内层循环的执行次数随外层循环的i值变化，逐个枚举i的取值：

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

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

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

推导时间复杂度 #

展开求和公式：n*(n+1)/2 = (1/2)n² + (1/2)n。

时间复杂度只保留最高阶项，忽略系数和低阶项，这里最高阶是n²，因此该函数的时间复杂度为O(n²)。

补充说明你的分析误区 #

你之前把内层循环的复杂度当成固定的(n-1)*?，是因为没注意到内层循环的次数随i递增而递减，不能用固定倍数计算，必须按i的每个取值累加次数。另外，外层循环的n次迭代不是单独的O(n)项，而是用来控制内层循环的次数，最终总复杂度由累加后的最高阶项决定。

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