2^n複雜度算法

我需要實現和測試一個2^n複雜度的算法。我一直在試圖找到一個。如果有什麼辦法可以通過實現來實現 - 具有2^n的確切複雜度將是最優的。如果有人知道一個位置，我可以找到一個例子，或者可以幫助我實現一個，這將是非常棒的:-)。基本的操作可以是任何事情，但像i ++這樣的單一語句;將是最好的。2^n複雜度算法

來源

2011-04-01 rubixibuc

+12

_「2^N的複雜性將是最佳」 _ LOL – wilhelmtell 2011-04-01 02:05:41

我曾經與曾的方式，使整個系統日誌功能的系統曾在爲O（n^n）的操作。我被告知，這很好，記錄不會影響應用程序「它只是記錄」，但計算出處理爲客戶提供的數據集，我被要求開展工作，我將需要大約64億年硬件I了。我只寫了一個SQL腳本生成器並在幾個小時內完成，也因爲沒有使用該公司的官方工具集而遭受了一場風波。 haaa good'ol記憶！ – Newtopian 2011-04-01 02:25:58

也許這是n !,我不記得確切 – Newtopian 2011-04-01 02:29:00

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

但你也應該查閱格雷碼。

來源

2011-04-01 02:19:04 user515430

謝謝:-)這是完美的，你知道我在哪裏可以找到一個樣本執行這個？ – rubixibuc 2011-04-01 02:29:27

或者我如何才能實現控件結構，並且只需爲語句執行i ++。 – rubixibuc 2011-04-01 02:29:55

我只是要上下投票看看獨角獸的舞蹈。 – Anycorn 2011-04-01 02:29:56

經典的遞歸斐波那契數的計算是O（2^n）。

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

由於上述實際上是THETA（披^ N），我添加一個THETA（2^n）的算法返回2^N。感謝耶利米威爾考克。

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

來源

2011-04-01 02:06:52 ThomasMcLeod

是不是隻有O（Fib（n）），它只有大約1.6^n？如果在底部用'Fib（n - 1）'代替'Fib（n - 2）'，它將變成2^n。 – 2011-04-01 02:09:19

@ Jeremiah，是的，從技術上講這個算法是θ（Phi^n），它在O（2^n）中。（Phi =（5 ^（1/2）+1）/ 2，約爲1.61。 – ThomasMcLeod 2011-04-01 02:14:06

這裏是輸出2 ^（2^n）的數字。

來源

2011-04-01 02:07:02 wnoise

Quantum Bogosort具有2^n空間複雜度。

來源

2011-04-01 02:10:29 wilhelmtell

很確定它有'n！'空間的複雜性 – 2011-12-05 22:39:48

我花了很多時間重新思考問題，並希望發佈一個我想出的解決方案。所有的答案都有助於我提出這個解決方案的能力，並且非常感謝每個人都回應。 :-)我意識到，算法幾乎沒有什麼。

它是用Java編寫
似乎無法獲得標籤的工作
基本操作是我++;

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

來源

2011-04-01 05:28:58 rubixibuc

2^n複雜度算法

回答

相關問題