为何genSubsets函数的时间复杂度是O(2ⁿ)而非O(n²)？

先看你给出的生成子集的函数：

def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]]
    smaller = genSubsets(L[:-1])
    extra = L[-1:]
    new = []
    for small in smaller:
        new.append(small+extra)
    return smaller+new

你之前的误区是只看到了单次循环和列表复制的O(n)，但忽略了递归过程中循环的次数是指数级增长的，具体原因如下：

1. 子集总数的基础：n个元素的集合，总共有2ⁿ个子集，这是函数最终要生成的结果数量，光是生成这么多子集，时间就不可能是O(n²)——比如n=20时，2²⁰已经超过百万，远大于20²=400。

2. 递归过程的操作量拆解：

   • 当处理长度为k的列表时，smaller是长度为2ᵏ⁻¹的列表（因为k-1个元素的子集数是2ᵏ⁻¹）。
   • 循环需要遍历这2ᵏ⁻¹个子集，每个子集执行small+extra的拼接操作，生成新的2ᵏ⁻¹个子集。
   • 把所有递归层级的循环次数加起来：1+2+4+...+2ⁿ⁻¹ = 2ⁿ - 1，这已经是O(2ⁿ)级别的操作次数。

3. 拼接操作的额外开销：
   每个small+extra的拼接时间和子集small的长度成正比，所有子集的总元素数是n×2ⁿ⁻¹（每个元素会出现在2ⁿ⁻¹个子集里），所以总时间复杂度实际是O(n×2ⁿ)，这比O(2ⁿ)更精确，但无论如何都是指数级复杂度，远高于你之前认为的O(n²)。

简单来说，你把递归里的循环次数当成了线性的n，但实际上每次递归的循环次数是翻倍增长的，最终总操作量是指数级的，而非二次方。

内容的提问来源于stack exchange，提问作者Zercon