Big O(2^n) 的这个解释是什么意思？

Question

我在 Skiena 的算法设计手册中阅读了有关大 Oh 符号的内容，并看到了 O(2ⁿ) 的以下解释：

Exponential functions: Functions like 2ⁿ arise when enumerating all subsets of n items.

具体例子是什么意思？

假设我有集合：{1,2,3,4}（因此 n=4），这意味着（根据 Skiena 的定义）子集的数量是 2⁴ 即 16 个子集。我想不通这 16 个子集是什么。

关系 2ⁿ 中的 2 是否意味着每个子集的大小限制为 2？

编辑：我想我要问的部分原因是，为什么 2ⁿ 而不是 3[例如=26=]n？这对我来说一点都不直观。

Answer 1

这是 {1, 2, 3, 4} 的所有有效子集的列表：

{}                                           1

{1}, {2}, {3}, {4}                        +  4

{1,2}, {1,3}, {1,4}, {2,3}, {2,4}, {3,4}  +  6

{1,2,3}, {1,2,4}, {1,3,4}, {2,3,4}        +  4

{1,2,3,4}                                 +  1

                                          = 16

计数是 2ⁿ 而不是 3ⁿ 的原因是要创建一个子集，您可以想象遍历每个元素并做出决定 "is the element in the subset or not?".

也就是说，您为每个 n 个元素在两种可能性（进和出）之间进行选择，因此做出此决定的方法总数（以及子集总数）为

    2 * 2 * 2 * .... * 2
    \________  ________/
             \/
           n times

也就是 2ⁿ.

Answer 2

0 个元素的一个子集：{}
1 个元素的四个子集：{1} {2} {3} {4}
2 个元素的 6 个子集：{1,2} {1,3} {1,4} {2,3} {2,4} {3,4}
3 个元素的四个子集：{1,2,3} {1,2,4} {1,3,4} {2,3,4}
4 个元素的一个子集{1,2,3,4}

子集总数因此为 16。

2n中的2简单的说就是"workload"按指数增长n 的函数。这甚至比 n2 更糟糕，它只是随平方上升。

这个由有限集的所有集合组成的集合称为 power set，如果您真的想知道为什么它是 2n，该页面的属性部分说明：

We write any subset of S in the format {X1, X2, ..., Xn} where Xi,1<=i<=n, can take the value of 0 or 1. If Xi = 1, the i-th element of S is in the subset; otherwise, the i-th element is not in the subset. Clearly the number of distinct subsets that can be constructed this way is 2n.

基本上，通俗地说，在给定的子集中，每个元素可以存在或不存在。因此，可能性的数量类似于您看到的 n 位二进制数。

对于一个比特，有两种可能性0/1，相当于集合{a}有子集{} {a}.

对于两个位，有四种可能性00/01/10/11，相当于集合{a,b}有子集{} {a} {b} {a,b}.

对于三个位，八种可能性000/001/010/011/100/101/110/111，相当于集合{a,b,c}有子集{} {a} {b} {c} {a,b} {a,c} {b,c} {a,b,c}.

依此类推，包括下一步的四个元素，给出上面已经看到的十六种可能性。

Big O(2^n) 的这个解释是什么意思？

What does this explanation of Big O(2^n) mean?

algorithm