2 ^ n复杂度算法

• Z时代
• 2024-01-10
• 分类：问答

我需要实现和测试2 ^ n复杂度的算法。我一直在努力寻找一个。如果有什么办法，我可以通过实现来达到目的-精确的2 ^

n复杂度将是最佳选择。如果有人知道某个位置，我可以找到一个示例，或者可以帮助我实现一个示例，那就太好了了:-)。基本操作可以是任何内容，但只能使用i

++之类的单个语句；最好。

回答：

生成具有n个元素的集合的所有子集。

添加。生成S = {a0，a1，…，an-1}的所有子集的最简单方法可能是在等级的二进制表示和子集之间进行转换。

取S = {a0，a1，a2}。

rank binary subset
0    000    {} 
1    001    {a0}
2    010    {a1}
3    011    {a0, a1}
4    100    {a2}
5    101    {a0, a2}
6    110    {a1, a2}
7    111    {a0, a1, a2}

因此，二进制中的1表示相应的元素在子集中。0表示元素不在子集中。

但是您还应该查找格雷码。

以上是 2 ^ n复杂度算法 的全部内容， 来源链接： utcz.com/qa/415423.html