嵌套循环的时间复杂度：请求计算并解释给定算法的时间复杂度

当然可以！咱们一步步拆解这个mystery(n)函数的时间复杂度，先把代码再贴一遍方便参考：

function mystery(n) 
    r := 0 
    for i := 1 to n − 1 do 
        for j := i + 1 to n do 
            for k := 1 to j do 
                r := r + 1 
    return(r) 

步骤1：理解每一层循环的执行次数 #

核心是计算r := r + 1这个操作总共执行了多少次——这就是算法时间复杂度对应的基本操作次数：

• 最内层循环（k循环）：k从1到j，每次执行j次操作。
• 中间层循环（j循环）：j从i+1到n，所以对于每个固定的i，中间层会触发内层循环n - i次，总操作次数是sum(j = i+1 to n) j（也就是从i+1到n的所有整数求和）。
• 最外层循环（i循环）：i从1到n-1，总的操作次数就是把每个i对应的中间层总次数加起来，也就是sum(i = 1 to n-1) [sum(j = i+1 to n) j]。

步骤2：展开求和式计算总次数 #

先计算内层的求和sum(j = i+1 to n) j：
我们知道从1到m的整数和是m(m+1)/2，所以：

sum(j=i+1 to n) j = sum(j=1 to n)j - sum(j=1 to i)j
= [n(n+1)/2] - [i(i+1)/2]
= (n² + n - i² - i)/2

接下来把这个结果代入外层求和：

总次数 = sum(i=1 to n-1) (n² + n - i² - i)/2
= (1/2) * [ sum(i=1 to n-1)(n² + n) - sum(i=1 to n-1)i² - sum(i=1 to n-1)i ]

分别计算每一部分：

1. sum(i=1 to n-1)(n² + n)：这是对i来说的常数项，总共加n-1次，结果是(n² + n)(n-1)
2. sum(i=1 to n-1)i：从1到n-1的整数和，结果是n(n-1)/2
3. sum(i=1 to n-1)i²：平方和公式，结果是(n-1)n(2n-1)/6

把这些代入后化简，最终可以得到总操作次数为：

总次数 = (n³ - n)/3

步骤3：确定时间复杂度 #

时间复杂度只关注最高次项，忽略系数和低次项。这里最高次项是n³，所以这个算法的时间复杂度是O(n³)——简单来说，随着n增大，函数的执行时间会以立方级别的速度增长。

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