我在阅读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ⁿ
。