Big Oの例2^n

Question

アルゴリズムの複雑さがn^cで、ループのネストされたものの数だけを描くことができます。

for (var i = 0; i < dataset.len; i++ { 
    for (var j = 0; j < dataset.len; j++) { 
     //do stuff with i and j 
    } 
} 

ログインが半分のたびに設定されているデータを分割何かで、バイナリ検索は、この（ように見えるこのためどのようなコード全くわからないが）ありません。

しかし、c^n、より具体的には2^nのアルゴリズムの簡単な例は何ですか。 O（2^n）はデータによるループに基づいていますか？またはデータの分割方法は？それとも全く別のもの？

Answer 1

実行時間O（2^N）のアルゴリズムは、サイズN-1の2つのより小さい問題を再帰的に解くことによってサイズNの問題を解決する再帰アルゴリズムです。

このプログラムは、例えば、擬似コードにおけるN個のディスクの有名な「タワーハノイの」課題を解決するために必要なすべての移動

void solve_hanoi(int N, string from_peg, string to_peg, string spare_peg) 
{ 
    if (N<1) { 
     return; 
    } 
    if (N>1) { 
     solve_hanoi(N-1, from_peg, spare_peg, to_peg); 
    } 
    print "move from " + from_peg + " to " + to_peg; 
    if (N>1) { 
     solve_hanoi(N-1, spare_peg, to_peg, from_peg); 
    } 
} 

レッツT（N）が要する時間であることを出力しN個のディスク。

我々は持っている：

T(1) = O(1) 
and 
T(N) = O(1) + 2*T(N-1) when N>1 

をあなたが繰り返し最後の項を展開すると、あなたが得る：

T(N) = 3*O(1) + 4*T(N-2) 
T(N) = 7*O(1) + 8*T(N-3) 
... 
T(N) = (2^(N-1)-1)*O(1) + (2^(N-1))*T(1) 
T(N) = (2^N - 1)*O(1) 
T(N) = O(2^N) 

を実際にこれを理解するには、あなただけの漸化式でその特定のパターンを知っている必要があります指数関数的な結果につながります。一般にT(N) = ... + C*T(N-1)とC > 1はO（x^N）を意味します。参照：

https://en.wikipedia.org/wiki/Recurrence_relation

Answer 2

可能な集合のすべての部分集合を反復する。この種のアルゴリズムは、例えば一般化されたナップザック問題のために使用される。

サブセットの繰り返しがどのようにO（2^n）に変換されるのか分かりにくい場合は、n個のスイッチのセットを想像してください。それぞれのスイッ​​チはセットの1つの要素に対応します。ここで、各スイッチをオンまたはオフにすることができます。サブセットにあると「オン」と考えてください。可能な組み合わせ数は2^nです。

コード内の例を見たい場合は、ここでは再帰について考えるのが簡単ですが、他のすばらしい例は考えられません。

Answer 3

int Fibonacci(int number) 
{ 
    if (number <= 1) return number; 

    return Fibonacci(number - 2) + Fibonacci(number - 1); 
} 

入力データセットごとに増加すると倍増します。 O（2N）関数の成長曲線は指数関数的であり、非常に浅く始まり、次に気象的に上昇する。 ビッグO（2^n）との私の例が、はるかに優れてはこれです：

public void solve(int n, String start, String auxiliary, String end) { 
    if (n == 1) { 
     System.out.println(start + " -> " + end); 
    } else { 
     solve(n - 1, start, end, auxiliary); 
     System.out.println(start + " -> " + end); 
     solve(n - 1, auxiliary, start, end); 
    } 

この方法のプログラムでは、「ハノイの塔」問題を解決するために、すべての動きを出力します。 どちらの例も問題を解決するために再帰的に使用しており、大きなO（2^n）の実行時間を持っていました。

Answer 4

C^N = cサイズのアルファベットからn要素のすべての組み合わせ。

より具体的には、2^NはすべてNビットで表現可能な数字です。これは実際には `O（N * 2^n）の`複雑である

vector<int> bits; 
int N 
void find_solution(int pos) { 
    if (pos == N) { 
    check_solution(); 
    return; 
    } 
    bits[pos] = 0; 
    find_solution(pos + 1); 
    bits[pos] = 1; 
    find_solution(pos + 1); 
}