J收缩为j= (j - 1) &i的循环的复杂性

Question

这个代码段的时间复杂度是多少？为什么，从数学上讲，是这样？

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

Answer 1

下面是一个Java代码片段：

int i,j,n,cnt;
int bit=10;
int[] mp = new int[bit+1];
n=(1<<bit);
for(i=0;i<n;i++){
   mp[Integer.bitCount(i)]++;
   if((i&i+1) ==0){ // check 2^k -1, all bit are set, max value of k bit num
       System.out.printf("\nfor %d\n",i);
       for(j=0;j<=bit;j++){
           System.out.printf("%d ",mp[j]);
       }
   }
}

输出：

for 0  // 2^0 - 1
1 0 0 0 0 0 0 0 0 0 0
for 1  // 2^1 - 1
1 1 0 0 0 0 0 0 0 0 0
for 3   // 2^2 - 1
1 2 1 0 0 0 0 0 0 0 0
for 7   // 2^3 - 1
1 3 3 1 0 0 0 0 0 0 0  
for 15  // 2^4 - 1
1 4 6 4 1 0 0 0 0 0 0
for 31  // 2^5 - 1
1 5 10 10 5 1 0 0 0 0 0
for 63   // 2^6 - 1
1 6 15 20 15 6 1 0 0 0 0 
for 127  // 2^7 - 1
1 7 21 35 35 21 7 1 0 0 0 
for 255  // 2^8 - 1
1 8 28 56 70 56 28 8 1 0 0 
for 511  // 2^9 - 1
1 9 36 84 126 126 84 36 9 1 0 
for 1023  // 2^10 - 1
1 10 45 120 210 252 210 120 45 10 1 

所以看起来像帕斯卡三角…

0C0 
1C0 1C1
2C0 2C1 2C2
3C0 3C1 3C2 3C3
4C0 4C1 4C2 4C3 4C4
5C0 5C1 5C2 5C3 5C4 5C5
6C0 6C1 6C2 6C3 6C4 6C5 6C6
7C0 7C1 7C2 7C3 7C4 7C5 7C6 7C7
8C0 8C1 8C2 8C3 8C4 8C5 8C6 8C7 8C8
9C0 9C1 9C2 9C3 9C4 9C5 9C6 9C7 9C8 9C9
10C0 10C1 10C2 10C3 10C4 10C5 10C6 10C7 10C8 10C9 10C10

在上述问题中，内循环精确执行2^(数字集位) -1次。因此，如果我们观察到，如果k=number of bit，那么N=2^k；

然后复杂性变成：(kC0_2^0+kC1_2^1+kC2_2^2+kC3_2^3+…)……+kCk*2^k) -N

如果是k=10，那么N=2^k=1024的复杂性如下：

(10C0*2^0+10C1*2^1+10C2*2^2+10C3*2^3+ … … … +10C10*2^10) - 1024 
=(1*1 +10*2 + 45*4+ 120*8+210*16+252*32+210*64+120*128+45*256+10*512+1*1024) - 1024
=59049 - 1024
=58025 

下面是另一个有助于验证数字58025的代码片段。

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

上述代码的输出为58025。