如何判定下述嵌套循环算法的时间复杂度？

首先把你的算法整理成清晰的代码形式：

S ← 0
for i = 1 to n do
    for j = 1 to i do
        S ← S + 1
    end for
end for
write(S)

接下来分析循环的执行次数：

• 外层循环i从1到n，一共执行n次。
• 每一次外层循环里，内层循环j的执行次数等于当前的i值：
  • 当i=1时，内层循环执行1次；
  • 当i=2时，内层循环执行2次；
  • ...
  • 当i=n时，内层循环执行n次。

所以内层循环的总执行次数是1+2+3+...+n，这是一个等差数列求和，公式为：
总次数 = n(n+1)/2

从时间复杂度的角度看，我们只关注最高阶项，忽略系数和低次项，所以这个算法的时间复杂度是O(n²)。

另外，变量S的最终值就是这个求和的结果，也就是n(n+1)/2。

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