algorithm - 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ⁿ 例如？这对我来说一点都不直观。

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ⁿ 的原因是要创建一个子集，您可以想象遍历每个元素并做出决定“是元素子集与否？”。

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

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

这是 2ⁿ。