2^n复杂度算法 [英] 2^n complexity algorithm

问题描述

我需要实现和测试一个复杂度为 2^n 的算法.我一直试图找到一个.如果有任何方法可以通过实现来实现这一点——精确的复杂度为 2^n，那将是最佳的.如果有人知道某个位置，我可以找到一个示例，或者可以帮助我实现一个示例，那就太棒了 :-).基本操作可以是任何东西，但像 i++ 这样的单个语句；最好.

I need to implement and test an algorithm with a 2^n complexity. I have been trying to find one for a while. If there is any way I can acheive this by implementation -- with a exact complexity of 2^n that would be optimal. If anyone knows of a location I can find an example, or could help me implement one, that would be awesome :-). The basic operation can be anything, but a single statment like i++; would be best.

推荐答案

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

Generate all subsets of a set with n elements.

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

Added. The simplest way of generating all the subsets of S = {a0, a1, ..., an-1} is probably to translate between the binary representation of the rank and the subset.

取 S = {a0, a1, a2}.

Take 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 表示该元素不在子集中.

So, a 1 in the binary means the corresponding element is in the subset. A 0 means the element is not in the subset.

但您也应该查找格雷码.

But you should also lookup Gray code.

这篇关于2^n复杂度算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！