请求协助计算给定C++函数的时间复杂度

目标函数代码 #

int func(int n) {
    int a = 0;
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j <= n - i; ++j) {
            for (int k = 0; k <= n - i; ++k) {
                for (int o = 1; o <= i; ++o) {
                    a++;
                }
            }
        }
    }
    return a;
}

复杂度推导过程 #

时间复杂度由最内层a++的执行次数决定，逐层分析循环逻辑：

• 最内层o循环：执行i次，每次完成1次a++操作。
• k循环：循环条件为k <= n-i，共执行(n - i + 1)次，每次触发完整的o循环，这部分总执行次数为(n - i + 1) * i。
• j循环：与k循环逻辑完全一致，同样执行(n - i + 1)次，每次触发完整的k循环及内层操作，总执行次数为i*(n - i + 1)²。
• 最外层i循环：从1到n遍历，因此a++的总执行次数为如下求和式：

  S(n) = Σ（i=1到n）[i*(n - i + 1)²]
  

求和式化简 #

令m = n - i + 1，当i从1到n时，m从n到1，求和式可等价转化为：

S(n) = Σ（m=1到n）[(n - m + 1)*m²]

展开后拆分求和项：

S(n) = (n+1)*Σ(m²) - Σ(m³) （m从1到n）

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

• Σ(m²) = n(n+1)(2n+1)/6
• Σ(m³) = [n(n+1)/2]²

代入计算并提取公因子化简后，最终得到精确的执行次数：

S(n) = n(n+1)²(n+2)/12

时间复杂度结论 #

当n趋近于无穷大时，表达式的最高次项为n⁴，因此该函数的时间复杂度为O(n⁴)。

如果你的推导是按照逐层统计循环次数、转化为求和式的思路推进，那么方向是完全正确的，最终化简后的结果也验证了这一推导逻辑的严谨性。

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