这个函数的时间/空间复杂度是多少?

Question

这是一个leetcode问题的解决方案:https://leetcode.com/problems/subsets/

我很难确定我的解决方案的时间/空间复杂性。

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)

任何想法?

Answer 1

完成的功与输出中某个列表中出现的(int)值的数量成线性关系。这是因为copy()的时间复杂度为0(𝑛)，其中𝑛是要复制的值的数目，而append()的时间复杂度为O(1)。

现在生成的列表可以被认为对应于一个二进制数。例如，输入[1,2,3]的结果是(在注释中使用二进制表示):

[
[       ],  # 000
[1      ],  # 100
[   2   ],  # 010
[1, 2   ],  # 110
[      3],  # 001
[1,    3],  # 101
[   2, 3],  # 011
[1, 2, 3]   # 111
]

每个列表中值的数目之和使得[1,2,3]中的每个数字恰好用于生成的列表的一半。列表的数量为2^𝑛(与3位组成的二进制数列表相比)。因此单个值出现的次数是𝑛2^𝑛-1，其中𝑛是输入列表的大小。

复杂度是O(𝑛2<一口>𝑛-1>𝑛>