求LeetCode subsets问题对应Python解法的时间与空间复杂度

你给出的实现代码如下：

def subsets(self, nums: List[int]) -> List[List[int]]:
    subsets = [[]]
    for num in range(len(nums)):
        subsets.append([nums[num]])
        for index in range(1, len(subsets) - 1):
             copy = subsets[index].copy()
             copy.append(nums[num])
             subsets.append(copy)
    return subsets

代码逻辑梳理 #

先简单过下这段代码的执行逻辑，方便理解复杂度的计算依据：
初始时结果列表里只有空集这一个子集，之后挨个处理nums里的每个数字：先把当前数字单独作为一个一元子集加进结果，再遍历之前已经生成的所有旧子集（刚加的那个单独数字子集不算），每个旧子集复制一份，把当前数字插入到拷贝的子集里，新生成的子集也加进结果。等所有数字处理完，结果列表里就包含了所有子集。

时间复杂度分析 #

我们设nums的长度为n：

• 长度为n的数组，所有子集的总数量固定为2^n个，这是子集问题的基础性质
• 生成每个新子集时，都需要做一次旧子集的拷贝操作，拷贝耗时和子集长度成正比。所有子集的元素总个数为n * 2^(n-1)（每个元素会出现在一半的子集里，总共有n个元素），对应的总拷贝耗时为O(n * 2^n)
• 嵌套循环的执行次数和子集总数成正比，循环本身的开销可以被拷贝操作的开销覆盖
  最终时间复杂度为O(n * 2^n)，这也是子集问题迭代解法的标准时间复杂度。

空间复杂度分析 #

分两种场景计算：

• 如果包含最终返回的子集结果的存储空间：所有子集的总元素个数为n * 2^(n-1)，对应空间复杂度为O(n * 2^n)
• 如果只统计算法执行过程中额外使用的临时空间（不算输出结果）：只有拷贝子集时用到的临时列表空间，最大的临时列表长度就是n，所以额外空间复杂度为O(n)

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