Beispiel eines großen O von 2^n

Question

So kann ich mir vorstellen, was ein Algorithmus ist, der eine Komplexität von n^c hat, nur die Anzahl der verschachtelten For-Schleifen.

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

Log etwas ist, das den Datensatz in die Hälfte jedes Mal teilt, binäre Suche funktioniert diese (nicht ganz sicher, welcher Code für das aussieht).

Aber was ist ein einfaches Beispiel für einen Algorithmus, der c^n oder genauer 2^n ist. Basiert O (2^n) auf Schleifen durch Daten? Oder wie Daten aufgeteilt werden? Oder etwas ganz anderes?

Answer 1

Algorithmen mit Laufzeit O (2^N) sind oft rekursive Algorithmen, die ein Problem der Größe N lösen, indem sie zwei kleinere Probleme der Größe N-1 rekursiv lösen.

Dieses Programm, zum Beispiel druckt alle Bewegungen notwendig, um den berühmten „Turm von Hanoi“ Problem für N Platten in Pseudo-Code

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

Let T (N) die Zeit, die für lösen N Festplatten.

Wir haben:

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

Wenn Sie wiederholt den letzten Begriff erweitern, erhalten Sie:

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) 

Um dies tatsächlich herauszufinden, man muss nur wissen, dass bestimmte Muster in der Rekursion führen zu exponentiellen Ergebnissen. Im Allgemeinen T(N) = ... + C*T(N-1) mit C > 1 bedeutet O (x^N). Siehe:

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

Answer 2

Denken Sie z.B. Iterieren über alle möglichen Teilmengen einer Menge. Diese Art von Algorithmen wird beispielsweise für ein generalisiertes Rucksackproblem verwendet.

Wenn Sie nicht verstehen können, wie die Iteration über Teilmengen in O (2^n) übersetzt wird, stellen Sie sich eine Menge von n Schaltern vor, von denen jeder einem Element einer Menge entspricht. Jetzt kann jeder der Schalter ein- oder ausgeschaltet werden. Denke an "on" als in der Teilmenge zu sein. Beachten Sie, wie viele Kombinationen möglich sind: 2^n.

Wenn Sie ein Beispiel im Code sehen wollen, ist es normalerweise einfacher, hier über Rekursion nachzudenken, aber ich kann gerade nicht an ein anderes schönes und unterstehendes Beispiel denken.

Answer 3

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

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

Das Wachstum verdoppelt sich mit jeder Addition zum Eingabedatensatz. Die Wachstumskurve einer O (2N) -Funktion ist exponentiell - sie beginnt sehr flach und steigt dann meteorisch an. Mein Beispiel von großen O (2^n), aber viel besser ist dies:

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

Bei diesem Verfahren Programm druckt alle bewegt "Tower of Hanoi" Problem zu lösen. Beide Beispiele verwenden rekursive, um das Problem zu lösen und hatten eine große O (2^n) Laufzeit.

Answer 4

c^N = Alle Kombinationen von n Elementen aus einem c großen Alphabet.

Genauer gesagt sind 2^N alle Zahlen, die mit N Bits dargestellt werden können.

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