求该算法复杂度for (i=1;i<1<<n;i++){for (j=i;j;j=(j-1)&i) // 求i的子集{...}}求该算法复杂度,最好还要证明,谢谢[解决办法]FM请查看一下私信
不是2进制有多少个1。注释写的挺清楚的，是枚举所有的子集。每个i如果有j个1的话，里层for就迭代2^j次。有j个1的二进制数有C(n,j)个，它需要迭代2^j次。加起来根据二项式定理，总共里层for迭代3^n次。
引用:不是2进制有多少个1。注释写的挺清楚的，是枚举所有的子集。每个i如果有j个1的话，里层for就迭代2^j次。有j个1的二进制数有C(n,j)个，它需要迭代2^j次。加起来根据二项式定理，总共里层for迭代3^n次。前面我能理解,复杂度为sum(j=1 to n,C(n,j)*2^j)，这是怎么推到3^n的?
