您好我一直在练习算法和数据结构，我解决了https://leetcode.com/problems/subsets/这是powerset函数，但似乎我的解决方案太慢了。这是代码：
def subsets(array):
set = [array]
n = len(array)
for i in range(n):
tmp_subsets = subsets(array[:i] + array[i+1:])
for subset in tmp_subsets:
if subset not in set:
set.append(subset)
return set
我知道还有其他更好/更快的解决方案，但我试图了解这个解决方案的时间和空间复杂性。
我认为这里的时间复杂度是O(n^n)，因为递归树每层都有n分支，n总分是否正确？
所以它比最佳的O(2^n)解决方案更糟糕。
我不确定空间复杂性，我的直觉说O(2^n)，但是当我绘制递归树时，它有点令人困惑，因为我在递归堆栈最大的点使用的空间是：
space_for_level(0)+space_for_level(1)+...+space_for_level(n)
n + (n-1) +...+ 1 = O(n^2)
但最终当我返回所有set的大小是O(2^n)所以我的空间复杂性将是O(2^n + n^2) = O(2^n)。
我的分析在时间和空间上都是正确的吗？任何能帮助我以更清晰的方式思考的指示都是值得欢迎的。
时间复杂
时间复杂度可以归结为以下递归关系：
T(n) = n * T(n-1) + n * 2^(n-1)
因为有一个主循环运行n次，每次剩余元素的子集（n-1）首先生成（T(n-1)）然后循环（2^(n-1)）。
注意，该关系假设循环中的每个其他操作都需要恒定的时间，这是一个合理的近似值，因为它的效果与n增长相当。例如这个操作：
if subset not in set
不需要花费恒定的时间（在列表长度上需要线性时间，一般来说set.append(subset)也不是常数），但是现在让我们忽略它（你得到了图片以及如何分析代码）。
递归关系表明复杂性至少是指数的。
空间复杂性
首先，生成n的所有子集，这意味着至少O(2^n)的复杂性。然而，由于在每个步骤期间递归和重新生成子集，空间复杂性不止于此。具体地，在每个循环步骤中生成一个运行的n-1子集的副本，然后将其扩充到原始子集。我们有：
S(n) = S(n-1) + 2^n
因为每次调用子集都会生成其余子集的1中间运行副本（即S(n-1)），并将它们组合成原始子集2^n。
请注意，我们不计算存储子集的每个项目所需的存储空间，这本身需要在O(n)附近存储复杂性，但为了简单起见，请考虑将其存储为O(1)（例如将子集存储为单词，二进制编码，对于小n <= 64）因此子集的整个存储（不计算辅助存储）将简单地为O(2^n)复杂度（否则，如注释中所述，存储复杂性以简单地存储n的所有子集是O(n 2^n)顺序）。
递归关系表明复杂性至少是指数的。
解
由于master theorem不能用于这些递归关系（如上所述），检查methods for solving first-order recurrence relations with variable coefficients以解决上述关系（空间复杂度就像算术级数，而时间复杂度具有更复杂的形式）并获得精确的复杂形式（尽管解决方案）可能非常复杂，它仍然是指数方式或其他方式）
更复杂
通过利用子集的结构和属性（给定明确的排序，例如词典），可以实现更好的时间和空间复杂性。
具体而言，已经生成的子集与其前任和后继者之间的亲密关系。因此，可以生成后继（序列中的下一个子集），只需对其前一个进行最小的更改（例如，仅添加或删除单个元素）。
例如，代码生成许多重复项，然后测试它们是否已经存在，这可以一起避免。此外，不需要递归，因此可以消除递归的时间和空间复杂性。此外，在主循环内只需要恒定存储（假设可以生成下一个子集，只对前一个子集进行最小的，恒定的变化量），依此类推。所有这些优化以一种方式利用子集的对称性和属性在确定的排序下。
PS。您还可以在computer.science.stackexchange上研究类似的问题，这些问题更充分地涉及算法复杂性