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

Question

我在Skiena的算法设计手册中读到了关于Big Oh符号的内容,并且遇到了O(2 ⁿ)的以下解释:

指数函数:在枚举n个项目的所有子集时出现类似2 ^n的函数.

这个具体例子意味着什么？

说我有集:{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?.