Python幂集生成代码时间复杂度疑问：O(n*2^n)还是O(n²*2^n)？

你对这段整数幂集生成代码的时间复杂度有疑问：官方及资料标注为O(n*2^{n)，但你分析后认为是O(n²*2}n)，咱们来拆解清楚：

先贴出代码：

from typing import List

class Solution:
    def subsets(self, nums: List[int]) -> List[List[int]]:
        n = len(nums)
        output = [[]]
        
        for num in nums: # 你认为这里是O(n)
            # 你认为合并列表是O(n)，循环执行2^n次，所以这里是O(n*2^n)
            output += [curr + [num] for curr in output]
        
        return output

你的问题出在对循环内操作的复杂度估算太笼统，不能直接把每轮操作都按O(n*2^n)计算，得逐轮看实际操作成本：

核心误区 #

你假设每次curr + [num]的操作是O(n)，但实际上这个操作的时间复杂度是当前curr的长度 + 1——因为要把curr里的所有元素和新元素拷贝到新列表里，并非固定的n。

逐轮计算总操作量 #

我们把每一轮循环的实际操作成本累加：

• 初始时，output仅含1个空列表
• 第1轮（处理第1个元素）：生成1个新列表，操作成本为0（空列表长度）+1=1，总操作量累计1
• 第2轮（处理第2个元素）：output有2个列表（空、[num1]），生成2个新列表，操作成本为(0+1)+(1+1)=3，总操作量累计1+3=4
• 第3轮（处理第3个元素）：output有4个列表，生成4个新列表，操作成本为(0+1)+(1+1)+(1+1)+(2+1)=8，总操作量累计4+8=12
• ...
• 第k轮（k从1到n）：此时output包含2^(k-1)个列表，生成新列表的总操作成本等于当前所有curr的总长度 + 2^(k-1)（每个新列表多1个元素）

而所有子集的总元素个数是**n2^{(n-1)**——因为每个元素会出现在2}(n-1)个子集里（剩下的n-1个元素可选可不选）。这段代码的所有拷贝操作，本质就是构建所有子集的元素，总操作量正好等于所有子集的总元素个数，也就是n2^{(n-1)，这属于O(n*2}n)的量级。

为什么不是O(n²*2^n)？ #

你错误地把外层循环的O(n)和每轮的O(n2^{n)相乘，但实际上每轮的操作量是递增的，总和是n*2}(n-1)，而非n(n2^{n)。比如n=3时总操作量是12，而n²*2}n=98=72，二者差了一个量级。

所以官方标注的O(n*2^n)是正确的。

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