求该算法复杂度,该如何解决

2012-09-10

求该算法复杂度for (i1i1ni++){for (jijj(j-1)&i)// 求i的子集{...}}求该算法复杂度,最好还要证

求该算法复杂度
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的?

[解决办法]
用二项式定理展开(x+2)^n，然后左右代入x=1