带有j终止条件的三层嵌套循环的时间复杂度求解

代码片段 #

for (int i = 1 to n) {
   for (int j = i to n) {
      for (int k = j  to n) {
         sum += a[i] * b[j] * c[k];  //O(1)
      }
      if (j == 2 * i) {
         j = n;
      }
   }
}

问题分析与推导 #

你整理的求和式，本质是将每个i对应的最内层k循环执行次数累加。我们可以把循环分为两类情况处理：当2i ≤ n时，j循环会在j=2i时提前终止；当2i > n时，j循环会完整执行。

分情况求和公式 #

1. 当n为偶数（n=2m）

总执行次数公式为：
$$S = \frac{2n^3 + 15n^2 + 10n}{24}$$

2. 当n为奇数（n=2m+1）

总执行次数公式为：
$$S = \frac{2n^3 + 15n^2 + 10n - 3}{24}$$

验证示例 #

• 当n=8（偶数）：代入公式得$\frac{2512 +1564 +10*8}{24} = 86$，与手动计算结果一致。
• 当n=9（奇数）：代入公式得$\frac{2729 +1581 +10*9 -3}{24}=115$，与手动计算结果一致。

统一表达式（可选） #

如果想用一个表达式覆盖奇偶情况，可以利用取模运算：
$$S = \frac{2n^3 +15n^2 +10n - 3*(n \mod 2)}{24}$$
其中n mod 2在n为奇数时取1，偶数时取0。

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