O(2^n)

一句话理解

O(2^n) 每个元素两条路，指数增长。

为什么要学

子集枚举、状压入门。

讲解

n=20 约一百万，n=30 约十亿。所以状压 n 常 ≤20。

2^n * n 也常见，n=20 大约 2e7，勉强。

例子

n 个开关，每个开或关，共 2^n 种状态。

常见错误

• n=40 还 2^n。
• 把 2*n 当成 2^n。