问题描述
我需要实现并用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复杂算法的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持!