algorithm - Set Cover 的蛮力复杂度

Question

我们可以通过形成所有可能的集合组合并验证它是否是最小解来解决集合覆盖问题。现在我们最多可以有 2^n 个这样的集合组合，其中 'n' 是集合的数量。

所以，这种方法的复杂度应该是 O(2^n)。然而，Wikipedia说“集合覆盖问题的复杂性是 m^n，其中 m 是宇宙的大小，n 是集合中集合的数量”。

谁能解释复杂度是 O(m^n) 而不是 O(2^n)？

提前致谢。

Answer 1

你几乎是对的；蛮力算法的复杂度为 O(m 2^n) 直到模型相关的对数因子，因为操纵这些集合不是免费的。 O(m^n) 可能来自这样的想法，即对于 m 个元素中的每一个，我们选择最多 n 个集合中的一个来覆盖它。我可以提供的最仁慈的可能解释是，主要来源为集合覆盖实例规定了 O(m^k) 的界限，其中每个元素最多属于 k 个集合，这是在近似算法上下文中考虑的一种特殊情况(存在多项式时间 k 近似)。