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

问题描述

我需要实现并用2的n次方的复杂测试的算法。我一直在试图找到一期一会。如果有什么办法可以实现达致这 - 与2的n次方一个确切的复杂性，这将是最佳的。如果有人知道一个位置，我可以找到一个例子，或可以帮助我实现一个，这将是真棒:-)。基本操作可以是任何东西，但像我++一个说明书;将是最好的。

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，...，一个-1}是可能的等级和子集的二进制重新presentation翻译

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.

但你也应该查找灰色code。

But you should also lookup Gray code.

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