我在阅读skiena算法设计手册中关于大oh符号的内容时,发现了以下关于o(2n)的解释:
指数函数:当枚举n个项的所有子集时,出现2n这样的函数。
这对于一个具体的例子来说意味着什么?
假设我有一个集合:{1,2,3,4}(因此n=4),这意味着(根据Skiena的定义)子集的数目是24,即16个子集我搞不清这16个子集是什么。
关系2n中的2是否意味着子集被限制为每个2的大小?
编辑:我想我要问的是,为什么是2N而不是3N?这对我来说一点也不直观。

最佳答案

下面是{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ⁿ

09-30 14:07
查看更多