时间戳

首页 > 解决方案 > 生成所有可能组合的分类和复杂性：P、NP、NP-Complete 或 NP-Hard

algorithm - 生成所有可能组合的分类和复杂性：P、NP、NP-Complete 或 NP-Hard

问题描述

该算法需要从给定列表中生成所有可能的组合（不包括空集）。

list          =>         [1, 2, 3]
combinations  =>         [{1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3}]

该算法将花费 O(2 n ) 时间复杂度来生成所有组合。但是，我不确定改进的算法是否可以降低时间复杂度。如果存在改进的算法，请分享您的知识！

如果它需要 O(2 n ) 是指数的，我想了解一下这个算法属于 P、NP、NP-Complete 或 NP-Hard 的哪个类。提前致谢 ：）

标签： algorithmtime-complexityp-np

解决方案

P、NP、NP-complete 和 NP-hard 都是决策问题的类别，其中没有一个包含涉及非二进制输出的问题（例如这个枚举问题）。

人们经常将FNP中的问题通俗地称为 NP 中的问题。这个问题也不存在于 FNP 中，因为关系的输出字符串的长度必须受输入长度的某个多项式函数的限制。这可能是 FNP 难的，但我们正在进入即使是研究生 CS 教育也无法涵盖的杂草。如果您足够关心，值得在 CS Stack Exchange 上询问。

推荐阅读