阿斯蒂芬小技巧——枚举子集时间复杂度证明

标签：斯蒂芬 复杂度 证明 枚举 子集 二项式

在写 状压dp 时，经常会见到如下句子：

for(int i=0;i<(1<<n);i++){
	for(int j=i;j!=0;j=(j-1)&i){
			
	}
}

时间复杂度证明如下：

单个 \(x\) 枚举子集复杂度易证( 设 \(y=log_2(x)\) )：

\[∑_{i=0}^{y} C^i_y \]

使用二项式定理：

\[(a+1)^n=∑_{i=0}^{n}C_n^i ~ a^i \]

将上面的 \(a\) 设为1，则有：

\[2^n=∑_{i=0}^{n}C_n^i \]

也就是说这一坨的复杂度就是 \(2^y\)：

\[∑_{i=0}^{y} C^i_y \]

接着将 \(x\) 分别取 \(0\)~\(2^n-1\)，复杂度即为：

PS:这里到 \(2^{n-1}\)是因为 \(2^{n-1}\) 最多有 \(n-1\) 个2

\[∑_{i=0}^{n-1} C^i_{n-1}~2^i \]

然后再使用二项式定理：

\[(a+1)^n=∑_{i=0}^{n}C_n^i ~ a^i \]

把 a=2 带进去会发现：

\[3^n=∑_{i=0}^{n}C_n^i ~ 2^i \]

于是就愉悦的证明出复杂度为：

\[3^{n-1} \]

耶耶耶耶耶耶！！

标签：斯蒂芬,复杂度,证明,枚举,子集,二项式
From： https://www.cnblogs.com/lewisak/p/18352308