子集 - Time/Space 分析

Question

问题是为给定的整数数组生成子集。
例如，
输入： [0, 1, 2]
输出： [ [], [0], [1], [2], [0,1], [0,2], [1, 2], [0, 1, 2]]
我需要帮助分析我解决此问题的时间和 space 复杂性。

时间复杂度
就像我知道子集的总数是 2^N 所以时间复杂度至少是 2 ^N 然后我的树的高度就像 N 的最坏情况一样，但随后我在依赖于 N 的 2 个嵌套循环内执行递归...所以我想知道我的时间复杂度是否会像 O(2^ N * N ^ 3）？好吧，如果是这样的话……我的代码很糟糕。

Space 复杂度
space 将消耗 2^N 行和最多 N 个元素，因此我知道 space 复杂度为 O(2^N * N)。

如果我有什么误解请告诉我！谢谢。

def powerset(array):
    # Write your code here.
    start_len = 0
    answer = [[]]
    while(start_len <= len(array)):
        i = 0
        while(i < len(array)):
            print(array[i:])
            powersetHelper([], array[i:], start_len, answer)
            i += 1
        start_len += 1
    print(answer)
    return answer


def powersetHelper(chosen, choices, target_len, answer):
    # Write your code here.
    chosen.append(choices[0])
    if(len(chosen) == target_len):
        if(chosen not in answer):
            answer.append(chosen)
    else:
        i = 1
        while(i < len(choices)):
            chosen_copy = chosen.copy()
            powersetHelper(chosen_copy, choices[i:], target_len, answer)
            i += 1

Answer 1

这段代码实际上是Ω(N * 4^N)（即至少是这个运行时），只是因为这两行

        if(chosen not in answer):
            answer.append(chosen)

每次添加新子集时，它都会对所有子集执行线性搜索。如果您的输入列表没有重复，并且您已经编写了 powerset 算法来避免重复，那么这些行是不必要的。无论哪种方式，使用 set() 而不是列表进行包含检查，因为这在运行时占主导地位。

Theta(N * 2^N)的space复杂度是正确的；如果您要存储所有子集，这是最佳选择。不幸的是，如果包含检查问题得到解决，我不知道代码的时间复杂度。看起来在powerset和powersetHelper中执行了大量不必要的工作和递归调用，我很难理解算法的逻辑。根据经验测试（将全局计数器放入函数中），修复包含检查后的操作数增长非常非常接近 n^2 * 2^n 的常数倍数。

子集 - Time/Space 分析

Subsets - Time/Space Analysis

python

algorithm

time-complexity

space-complexity