使用Θ记号分析三层嵌套循环算法的时间复杂度

开发者阿泽

2026-10-1

算法时间复杂度分析

首先贴出修正了语法问题的目标代码：

int fun(int n) {
    int sum = 0;
    for (int i = n; i > 0; i--) {
        for (int j = i; j < n; j *= 2) {
            for (int k = 0; k < j; k++) {
                sum += 1;
            }
        }
    }
    return sum;
}

逐层循环分析

我们从最内层向外逐层计算执行次数：

最内层k循环：对于固定的j，循环会执行恰好j次，时间开销和j线性相关。
中层j循环：从j=i开始，每次乘2直到j≥n停止，取值序列为i, 2i, 4i, ..., 2^m *i，其中2^m *i <n ≤ 2^{m+1}*i。把这层所有j对应的k循环次数加总，得到固定i对应的总内层执行次数：
```
i + 2i +4i + ... + 2^m *i = i*(2^{m+1} -1)
```
结合2^m *i <n的约束，这个求和结果严格小于2n，上界是O(n)，下界是Ω(i)。
外层i循环：i从n递减到1，我们把所有i对应的中层+内层执行次数加总得到总开销。

总开销求和与大Θ推导

我们可以用分区间求和的方式简化计算：按2的幂次把i的取值划分为log₂n个区间，第t个区间为i ∈ [n/2^t, n/2^{t-1})，t从1到log₂n。

每个区间内的i对应的中层循环执行t次，区间长度为n/2^t
单个区间的总执行次数约为(2^t) * 平均i * 区间长度 ≈ 2^t * (3n/2^{t+1}) * (n/2^t) = 3n²/2^{t+1}
把所有区间的贡献加总，得到总次数约为3n²/2 * sum_{t=1}^{log₂n} 1/2^t，这个等比数列求和结果收敛到小于1的常数，因此总开销的上界是O(n²)。
再看下界：取i从1到n/2，每个i对应的执行次数至少为i，求和结果为n(n/2 +1)/4 = Ω(n²)。
上下界匹配，因此算法的时间复杂度为Θ(n²)。