含j=(j-1)&i的嵌套循环代码时间复杂度是多少？如何数学推导？

代码片段 #

for (int i = 0; i < n; i++) {
    for (int j = i; j > 0; j = (j - 1) & i) {
        System.out.println(j);
    }
}

时间复杂度结论 #

这段代码的时间复杂度为 **O(n^{log₂3)**（约等于O(n}1.585)）。

数学推导过程 #

1. 内层循环的执行次数分析 #

内层循环中，j = (j - 1) & i 的核心作用是枚举i的二进制表示中所有非空的1位子集：

• 若i的二进制包含k个1，那么i的非空1位子集共有 2ᵏ - 1 个（每个1位可选或不选，排除全不选的空集情况）。
• 举例：i=5（二进制101，k=2），内层循环会输出5(101)、4(100)、1(001)，共2²-1=3次，完全符合这个规律。

因此，每个i对应的内层循环执行次数为 2ᵏ - 1，其中k是i的二进制中1的个数。

2. 总执行次数的求和 #

代码的总操作次数等于i从0到n-1的内层循环次数之和：
$$
\text{总次数} = \sum_{i=0}^{n-1} (2^{count_1(i)} - 1) = \sum_{i=0}^{n-1}2{count_1(i)} - n
$$
其中count_1(i)表示i的二进制中1的个数。

3. 求和项的上界推导 #

关键是计算 $\sum_{i=0}^{n-1}2{count_1(i)}$ 的渐近上界：

• 当n是2的幂（即n=2ᵐ）时，0到n-1的二进制恰好是m位的所有可能组合。对于每个二进制位，我们可以选择该位为0（贡献因子1）或1（贡献因子2），因此总和为 $(1+2)^m = 3^m$。而 $3^m = (2^m){log₂3} = n^{log₂3}$。
• 当n不是2的幂时，设n介于2ᵐ和2ᵐ⁺¹之间，此时总和不会超过 $3^{m+1} = 33^m < 3n^{{log₂3}$，仍属于O(n}log₂3)的范畴。

4. 最终复杂度 #

减去n后（n相对于n^{log₂3是低阶项，可忽略），总次数的渐近复杂度为O(n}log₂3)。

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