python - 子集生成算法的时间复杂度

Question

以下代码的算法复杂度为 O(2^n)

def genSubsets(L):
    res = []
    if len(L) == 0:
        return [[]]
    smaller = genSubsets(L[:-1]) # find all subsets without last element
    extra = L[-1:] # create a list of just last element
    new = []
    for small in smaller:
        new.append(small+extra) # for all smaller solutions, add one with last element
    return smaller + new # combine those with last element and those without

# Given explanation: For a list of size n there are 2^n cases ---> O(2^n) <huh?>

我不明白长度为 n 的列表怎么会有 2^n 种情况。

这是我的理解:

• 长度为 n 的列表将进行 n 次递归调用(每次调用都传递一个没有最后一个元素的列表 --> 完成直到空列表 [ ])。这是 O(n) 复杂度
• 然后你开始递归调用
• 随着您向上移动，解决的子问题数量(“较小”列表)增加，因此每次递归调用中完成的循环量增加
• “更小”的列表大小(从最深的递归调用开始):0、1、2、4、8、16 ...
• 操作总数 0 + 1 + 2 + 4 + ...2^n(因为有 n 个递归)
• O(2^n)

这个解释有道理吗？ (大声笑，我在写这篇文章时回答了我的问题，但一些外部知识会有所帮助 XD)

Answer 1

I don't understand how there are 2^n cases for a list of length n.

• 好的，在这种情况下，要检查每个可能的子集，我们要么 take the current element在迭代中或者我们 don't take current element在迭代中。

• 这为我们带来了每个元素的 2 个案例 -> 接受或不接受。

  对于下面的树，我将表示 take作为T和 Don't take作为DT .

让我们考虑这个数组=> [1,3,5] .递归树看起来像这样-

                               Start state
                               /          \
                              /            \
                             /              \
                          T-1                DT-1
                         /   \               /   \
                        /     \             /     \
                       /       \           /       \
                      /         \         /         \
                     T-3      DT-3      T-3         DT-3
                    / \        /  \      / \         /  \
                   /   \      /    \    /   \       /    \
                  T-5  DT-5 T-5  DT-5  T-5  DT-5   T-5   DT-5

• 从上面的树可以看出，有 2³ 个叶子定义了 2³ 个子集可能性 。您可以为大于 3 的输入创建这样的递归树，以了解为什么在这种情况下复杂度是指数级的 (2ⁿ)。

• 您可以通过从根遍历到每个叶子来检测这棵树的任何子集。

  例如- [Start state,T-1,DT-3,T-5]表示子集 [1,5] .