2 ^ n复杂度算法

Question

我需要实现并测试具有2 ^ n复杂度的算法.我一直试图找到一个.如果有任何方法我可以通过实现来实现这一点 - 具有2 ^ n的精确复杂度将是最佳的.如果有人知道某个位置我可以找到一个例子,或者可以帮助我实现一个,这将是很棒的:-).基本操作可以是任何东西,但是像i ++这样的单一陈述; 会是最好的.

Answer 1

生成具有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表示该元素不在子集中.

但你也应该查找格雷码.

Answer 2

经典的递归Fibonacci数计算是O(2 ^ n).

unsigned Fib(unsigned n)
{
    if (n <= 1)
        return n;
    else
        return Fib(n - 1) + Fib(n - 2);
}

由于以上实际上是theta(Phi ^ n),我正在添加一个返回2 ^ n的theta(2 ^ n)算法.感谢Jeremiah Willcock.

unsigned TwoExp(unsigned n)
{
    if (n == 0)
        return 1;
    else
        return TwoExp(n - 1) + TwoExp(n - 1);
}

Answer 3

量子 Bogosort 的空间复杂度为 2^n。