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

经典的递归斐波那契数计算是 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) 算法。感谢耶利米·威尔科克。

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

Answer 3

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

Answer 4

我花了很多时间重新思考这个问题，并想发布我想出的解决方案。所有的答案都有助于我提出这个解决方案，并且非常感谢每个回复的人。 :-) 我意识到算法实际上什么也没做。

它是用java编写的
似乎无法让选项卡工作
基本操作是i++；

public class TwoToTheN
{  
     private static int twoToTheN = 0;  
     private static int power = 3;

     public static void main(String[] args)   
     {  
         twoToTheN(power);  
         System.out.println(twoToTheN);  
     }  

     private static void twoToTheN(int n)  
     {  
         if(n == 0)   
         {  
             twoToTheN++;  
             return;  
         } 
         else if(n == 1)  
         {  
             twoToTheN++;  
             twoToTheN++;  
             return;  
         }  
         twoToTheN(n-1);  
         twoToTheN(n-1);  
     }
}  

Answer 5

其一：输出 2^(2^n) 的数字。