algorithm - Set Cover的蛮力复杂性

我们可以通过形成所有可能的集合组合并验证它是否是最小解来解决集合覆盖问题。现在我们最多可以有2^n个这样的集合组合，其中'n'是集合的数目。
因此，这种方法的复杂性应该是O（2 ^ n）。然而，表示集覆盖问题的复杂性是M^ n，其中m是宇宙的大小，n是集合中集合的个数。
有人能解释复杂性是O（m^ n）而不是O（2 ^ n）吗？
提前谢谢。

最佳答案

你几乎是对的，蛮力算法的复杂性是O（m 2 ^ n）到模型依赖的日志因素，因为操作那些集合不是免费的。o（m^n）可能来自这样一个想法：对于m个元素中的每一个，我们选择最多n个集合中的一个来覆盖它。我可以提供的最慈善的可能解释是，主要源陈述了集合覆盖的实例的O（m^ k）的界限，其中每个元素属于至多k个集合，在近似算法的上下文中考虑的特殊情况（有多项式时间k近似）。

关于algorithm - Set Cover的蛮力复杂性，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/26400763/