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

Question

通常，在处理组合时，Big-O 复杂度似乎是O(n 选择 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 select t) 算法吗？如果不是，那是什么以及为什么？

Answer 1

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

• 每个项目都可以选择或不选择。

• 这是您的 θ(n 选择 k)，只是对所有 k 进行总结。

---

更精确的界限将同时考虑n和目标总和t。在这种情况下，按照上面第二点的推理，如果所有元素(和目标总和)都是正整数，那么复杂度将是 θ(n 选择 k) 对于 k 的总和仅达到 t。