关于子集枚举的时间复杂度证明

Posted on Edited on In Word count in article: 319 Reading time ≈ 1 mins.
RT

最近不知道为什么，感觉很多题多需要有子集枚举这样的操作来做一些优化，然后就不太会分析这个时间复杂度，这里就是简单证明一下啊。

1
2
3
for (int i = 0; i <= ((1 << len) - 1); ++i)
  for (int sta = i; sta; sta = (sta - 1) & i)
    do something;

就是这样的一个玩意，为什么它的时间复杂度是 \(O(3^{len})\) 呢？

简单证明

对于一个有 \(i\) 个 \(1\) 的数来说（二进制下），它被枚举到的次数应该为：\(\binom ni2^{len-i}\) ，感觉这个还是可以理解的。

然后就是说，要考虑到所有的情况，所以所有数的代价就应该是 ：

\[ \begin{aligned} sum&=\sum\limits_{i=0}^{len}\binom {len}i2^{len-i}\\ &=\sum_{i=0}^{len}\binom{len}{len-i}2^{len-i}\\ &=\sum_{i=0}^{len}\binom{len}i2^i \end{aligned} \]

然后在考虑一个二项式展开：

\[ (1+x)^{len}=\sum_{i=0}^{len}\binom {len}ix^i \]

所以就会有一个十分惊奇的发现：\(x=2\) 时，刚好和上面的退下来的那个玩意儿相等了。

所以就可以就可以得到这样的一个结论： \[ \begin{aligned} sum&=\sum_{i=0}^{len}\binom {len}i2^i\\ &=(1+x)^{len}\\ &=(1+2)^{len}=3^{len} \end{aligned} \] 证毕！

终于可以快乐的子集枚举了。