这个 powerset 函数的时间和 space 复杂度是多少？

Question

你好，我一直在练习算法和数据结构，我解决了 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

我知道还有其他 better/faster 解决方案，但我想了解这个解决方案的时间和 space 复杂性。

我认为这里的时间复杂度是 O(n^n)，因为递归树每个级别有 n 个分支，总共 n 个级别是否正确？

所以它比最优 O(2^n) 解决方案更差。

虽然我不确定 space 的复杂性，但我的直觉是 O(2^n) 但是当我画出递归树时它有点混乱，因为 space 我在我的递归堆栈最大的点是：

space_for_level(0)+space_for_level(1)+...+space_for_level(n)
n + (n-1) +...+ 1 = O(n^2)

但最后当我 return 所有东西 set 的大小都是 O(2^n) 所以我的 space 复杂度将是 O(2^n + n^2) = O(2^n).

我对时间和 space 的分析是否正确？欢迎任何帮助我以更清晰的方式思考的指针。

Answer 1

时间复杂度

时间复杂度可以总结为如下递归关系：

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)通常不是常数时间），但暂时忽略它（你得到图片以及如何分析代码）。

递推关系表明复杂性至少呈指数级。

Space复杂度

首先，生成n的所有子集，这意味着至少O(2^n)的复杂度。然而，由于在每个步骤中递归和重新生成子集，space 的复杂性远不止于此。具体来说，在每个循环步骤中，生成 n-1 的子集的一个运行副本，然后扩充到原始子集。我们有：

S(n) = S(n-1) + 2^n

因为每次调用 subset 都会生成 1 中间运行副本 剩余子集（即 S(n-1)） 加上它 将它们组合成 2^n.

的原始子集

注意我们不计算存储子集的每个项目所需的存储，它本身需要大约 O(n) 的存储复杂度，但考虑到这一点为简单起见 O(1) 的常量存储（例如，将子集存储为一个字，以二进制编码，对于小的 n <= 64），因此子集的整个存储（不计算辅助存储）将很简单O(2^n) 复杂度（否则，如评论中所述，简单存储 n 的所有子集的存储复杂度为 O(n 2^n) 阶）。

递推关系表明复杂性至少呈指数级。

解决方案

由于master theorem cannot be applied for these recurrence relations (as noted), check methods for solving first-order recurrence relations with variable coefficients为了解决上述关系（space复杂度就像一个等差级数，而时间复杂度有更复杂的形式）并获得精确的复杂度形式（虽然解决方案可能非常复杂，它仍然会以一种或另一种方式呈指数增长）

更复杂

更好的时间和space复杂性可以通过利用子集的结构和属性来实现（给定一个明确的顺序，例如词典).

特别是已经生成的子集与其前任和继任者之间的密切关系。因此，后继者（序列中的下一个子集）可以 生成，只需对其前任 进行最小的更改（例如，仅添加或删除单个元素）。

例如，代码生成许多重复项，然后测试它们是否已经存在，这可以完全避免。加上不需要递归，因此可以消除递归的时间和space复杂性。此外，在主循环中只需要 常量存储 （假设可以生成下一个子集，只需对前一个子集进行最小的、恒定的更改）等等。所有这些优化都以一种或另一种方式利用了确定顺序下子集的对称性和属性。

PS。你也可以在computer.science.stackexchange上研究更全面的算法复杂度的类似问题

这个 powerset 函数的时间和 space 复杂度是多少？

What are the time and space complexities of this powerset function?

python-3.x

recursion

time-complexity

space-complexity

powerset