2^n 复杂度算法

Question

我需要实现并测试一个2^n复杂度的算法。我已经试图找了一段时间的算法。如果有任何办法能够通过实现来达到精确的2^n复杂度，那将是最优的。如果有人知道我可以找到例子的地方，或者可以帮我实现一个例子，那就太好了。基本操作可以是任何东西，但像 i++ 这样的单个语句最好。

- rubixibuc

---

"2的n次方的复杂度将是最优的"。LOL - wilhelmtell

我曾经使用过一个系统，它的日志记录实现方式使整个系统的操作时间复杂度达到了O(n^n)。有人告诉我这已经足够好了，因为日志记录不可能影响应用程序的性能，“只是日志记录”而已。但是我计算出来，要处理客户要求的数据集，我需要在我手头的硬件上花费大约64亿年的时间。最后我写了一个SQL脚本生成器，在几个小时内完成了任务，但因为没有使用公司的官方工具集，我也遭受了一场风暴般的批评。哈哈，好怀念啊！ - Newtopian

这显然是一份作业；没关系，但请将其标记为作业。谢谢。 - j_random_hacker

@Newtopian 你确定它不是 n^2 吗？我无法想象你如何在 n^n 的时间内登录。 - Nick Johnson

@Nick 信不信由你，自制的日志记录系统将所有先前的日志语句保存在内存中，每次添加一个日志时，它都会遍历列表并为每个条目再次执行日志记录操作。嗯，我应该说它是一个可重入循环，所以要将D记录到文件中，它会记录A（再次），然后记录A，A和B，然后是A，AB和ABC，然后是A，AB，ABC和ABCD，并为每个条目再次执行所有格式化操作。不用说，日志文件增长非常快！... 嗯，想想看，你是对的，它不是n^n而是(n-1)!...我的错 :-) - Newtopian

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

但您还应该查找格雷码。

- user515430

---

谢谢 :-) 很完美，您知道在哪里可以找到这个的样例实现吗？ - rubixibuc

或者我可以只实现控制结构，然后对语句执行 i++。 - rubixibuc

我只是会给你点赞或踩一下，看看独角兽跳舞。 - Anycorn

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)，我添加了一个时间复杂度为theta(2^n)的算法来返回2^n。感谢Jeremiah Willcock。

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

- ThomasMcLeod

---

难道它不只是O(Fib(n))，这只有大约1.6^n吗？如果你在底部将Fib(n-2)替换为Fib(n-1)，那么复杂度会变成2^n。 - Jeremiah Willcock

@Jeremiah，是的，从技术上讲，这个算法是theta(Phi^n)，也就是O(2^n)。(Phi = (5^(1/2) + 1) / 2，约为1.61。 - ThomasMcLeod

Answer 3

Quantum Bogosort具有2的n次方的空间复杂度。

- wilhelmtell

---

很确定它的空间复杂度是n!。 - Nick Johnson

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);  
     }
}  

- rubixibuc

Answer 5

这里有一个问题：输出2^(2^n)的数字。

- wnoise