algorithm - 子集和枚举的时间复杂度

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

如果重点是根据集合大小给出最差的复杂度，n，那么它是Θ(2ⁿ)。给定任何集合，如果目标总和足够大，您将最终枚举该集合的所有可能子集。这是 Θ(2ⁿ)，可以通过两种方式看出:

• 每一项都可以选择，也可以不选择。

• 这是您的 Θ(n 选择 k)，只是对所有 k 求和。

---

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