为什么枚举子集是 O(3^n)

最编程 2024-04-22 10:33:57

...

枚举子集为什么是 \(O(3^n)\) 的 .

考虑一种常见的枚举子集方式：

for (int s = u; s; s = (s - 1) & u) {
	// s 是 u 的一个非空子集 
}

显然单次枚举 \(S\) 的一个子集是 \(O(2^{|S|})\) 的 .

为什么枚举 \(S\) 的所有子集的子集的时间复杂度是 \(O(3^n)\) 的 .

显然枚举大小为 \(n\) 的集合 \(S\) 的复杂度是

\[O\left(\sum_{T\subseteq S}2^{|T|}\right) \]

不难发现，\(S\) 中大小为 \(l\) 的子集个数是 \(\dbinom nl\)，这是简单的组合数学知识 .

转而枚举 \(l\)，于是原式就化为

\[O\left(\sum_{i=1}^n\dbinom ni 2^i\right) \]

然后里面这个东西可以由众所周知的谔项式定理化简

\[\begin{aligned}\sum_{i=1}^n\dbinom ni 2^i&=\sum_{i=1}^n\dbinom ni 2^i1^{n-i}\\&=1 + (1+2)^n\\&=O(3^n)\end{aligned} \]

于是，枚举 \(S\) 的所有子集的子集的时间复杂度是 \(O(3^n)\) 的 .

证毕 .

感谢 SoyTony 神仙的指导 orz

感谢 fjy666 神仙的指导 orz