嘿，我来帮你一步步拆解这个三层循环的执行次数和时间复杂度，这样你就能清楚搞明白啦！

首先先把你的代码贴出来方便参考：

for(int i =1; i<=n; i++){ 
    for (int j=i; j<=n; j++) { 
        for (int k =1; k<=j; k++){ 
            // Any statement 
        } 
    } 
}

我们从最内层开始逐层推导，最终算出总执行次数和时间复杂度：

步骤1：固定i和j，计算最内层循环次数 #

当i和j的取值固定时，k从1遍历到j，所以最内层循环每次会执行j次。

步骤2：固定i，计算中间层+最内层的总次数 #

对于每个固定的i，j的取值范围是从i到n。我们需要把每个j对应的最内层执行次数累加，也就是计算这个求和式：
$$\sum_{j=i}^{n} j$$
这是标准的等差数列求和，首项为i，末项为n，项数为n-i+1，求和结果可以简化为：
$$\sum_{j=i}^{n} j = \frac{n(n+1)}{2} - \frac{(i-1)i}{2} = \frac{n^2 + n - i^2 + i}{2}$$

步骤3：遍历所有i，计算全局总执行次数 #

接下来我们把每个i对应的次数全部加起来，得到总执行次数T(n)：
$$T(n) = \sum_{i=1}^{n} \frac{n^2 + n - i^2 + i}{2}$$

把式子拆分后分别计算每个求和项：
$$T(n) = \frac{1}{2} \left[ \sum_{i=1}^{n}(n2 + n) - \sum_{i=1}^{n}i2 + \sum_{i=1}^{n}i \right]$$

代入已知的数学求和公式：

• $\sum_{i=1}^{n}(n2 + n) = n(n^2 + n) = n^3 + n^2$
• $\sum_{i=1}^{n}i2 = \frac{n(n+1)(2n+1)}{6}$
• $\sum_{i=1}^{n}i = \frac{n(n+1)}{2}$

经过化简后，最终得到总执行次数的表达式：
$$T(n) = \frac{2n^3 + 3n^2 + n}{6} = \frac{n(n+1)(2n+1)}{6}$$

步骤4：推导时间复杂度 #

观察总次数的表达式，最高次项是$\frac{2n^3}{6} = \frac{n^3}{3}$。根据大O符号的定义，我们可以忽略系数和低次项，所以这段代码的时间复杂度是O(n³)。

小例子验证 #

我们用几个小的n值验证一下，确保推导正确：

• 当n=1时，总次数=1，公式计算：$\frac{123}{6}=1$，正确。
• 当n=2时，总次数=1+2+2=5，公式计算：$\frac{235}{6}=5$，正确。
• 当n=3时，总次数=1+2+3+2+3+3=14，公式计算：$\frac{347}{6}=14$，正确。

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