带条件的三层嵌套循环的时间复杂度（大O表示法）如何计算？

int DAA(int n){
    int i, j, k, x = 0;
    for(i=1; i <= n; i++){
        for(j=1; j <= i*i; j++){
            if(j % i == 0){
                for(k=1; k <= j; k++){
                    x += 10;
                }
            }
        }
    }
    return x;
}

你给出的代码的时间复杂度为O(n⁴)，你初步推测的O(n³)不匹配当前代码，但如果代码中第三层循环的终止条件为k <= i的话，时间复杂度就是O(n³)，和你的推测一致。

我们只统计影响复杂度的高阶增长项，常数操作和低阶项在大O表示法中可忽略：

• 第一层循环i从1遍历到n，共执行n次，我们单独计算每个固定i对应的内部操作量，最后累加所有i的结果即可。
• 第二层循环j从1遍历到i²，共i²次迭代：
  • 每次迭代都会执行一次j%i == 0的判断，这部分操作的总次数累加所有i的结果为sum_{i=1}^n i² = O(n³)，属于低阶项。
  • 只有当j是i的倍数时才会进入第三层循环，在1到i²范围内，i的倍数共有i个，分别为i、2i、3i...i*i。
• 第三层循环的执行次数：对每个符合条件的j，循环会执行j次，因此固定i时第三层循环的总次数为：
  sum_{m=1}^i (m*i) = i * sum_{m=1}^i m = i * i(i+1)/2 = (i³ + i²)/2
• 总高阶项计算：将所有i的第三层循环次数累加，得到最高阶项为：
  sum_{i=1}^n i³/2 = O(n⁴)
O(n⁴)的增长阶远高于O(n³)，因此当前代码的最终时间复杂度为O(n⁴)。

内容的提问来源于stack exchange，提问作者Achraf Ben Soltane