子集和枚举的时间复杂度

Question

通常，在处理组合时，Big-O 复杂度似乎是 O(n choose k)。在此算法中，我生成数组中与目标总和相匹配的所有组合：

def combos(candidates,start, target):
    if target == 0:
        return [[]]
    res = []
    for i in range(start,len(candidates)):
        for c in combos(candidates, i+1, target-candidates[i]):
            res.append([candidates[i]]+ c)
    return res


print combos([2,1,10,5,6,4], 10)
# [[1, 5, 4], [10], [6, 4]]

我在这里很难确定 Big-O，这是 O(n choose t) 算法吗？如果不是，那是什么，为什么？

Answer 1

如果重点是根据集合大小给出worst-cast复杂度，n，那么就是Θ(2ⁿ)。给定任何集合，如果目标总和足够大，您将最终枚举该集合的所有可能子集。这就是Θ(2ⁿ)，从两个方面可以看出：

每一项可有可无
就是你的Θ(n选k)，只是总结了所有k.

更精确的边界将同时考虑 n 和目标总和 t。在这种情况下，按照上面第 2 点的推理，如果所有元素（和目标总和）都是正整数，那么复杂度将是 Θ(n choose k) 的总和对于 k 仅求和 t.

Answer 2

你的算法至少是 O(2^n)，我相信是 O(n * 2^n)。这里有一个解释。

在您的算法中，您必须生成一个集合的所有可能组合（空集合除外）。所以这是：

O(2^n) 至少。现在对于每种组合，您都必须将它们相加。一些集合的长度为 1，长度为 n，但其中大多数的长度为 n/2。所以我相信你的复杂度接近 O(n * 2^n).

子集和枚举的时间复杂度

Time Complexity of Subset-Sum Enumeration

algorithm

big-o

enumeration

subset-sum