Esempio di Big O di 2^n

Question

Quindi posso immaginare cosa sia un algoritmo che ha una complessità di n^c, solo il numero di cicli annidati.

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

Log è qualcosa che divide il set di dati a metà ogni volta, ricerca binaria fa questo (non del tutto sicuro di quello che il codice per questo sembra).

Ma quale è un semplice esempio di un algoritmo che è c^n o più specificamente 2^n. O (2^n) è basato su cicli attraverso i dati? O come vengono divisi i dati? O qualcos'altro interamente?

Answer 1

Algoritmi con tempo di esecuzione O (2^N) sono spesso algoritmi ricorsivi che risolvono un problema di dimensione N risolvendo ricorsivamente due problemi minori di dimensione N-1.

Questo programma, per esempio, stampa tutte le mosse necessarie per risolvere le famose "Torri di Hanoi" problema per N dischi in pseudo-codice

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

Sia T (N) sia il tempo necessario per N dischi.

abbiamo:

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

Se si espande più volte l'ultimo termine, si ottiene:

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) 

Per capire davvero questo fuori, devi solo sapere che certi schemi nella relazione di ricorrenza portare a risultati esponenziali. Generalmente T(N) = ... + C*T(N-1) con C > 1 significa O (x^N). Vedere:

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

Answer 2

Pensa ad es. iterando su tutti i possibili sottoinsiemi di un set. Questo tipo di algoritmi viene utilizzato ad esempio per un problema di zaino generalizzato.

Se hai difficoltà a capire come l'iterazione su sottoinsiemi si traduca in O (2^n), immagina un insieme di n interruttori, ognuno dei quali corrisponde a un elemento di un set. Ora, ciascuno degli interruttori può essere attivato o disattivato. Pensa a "on" come nel sottoinsieme. Nota, quante combinazioni sono possibili: 2^n.

Se si desidera vedere un esempio di codice, in genere è più semplice pensare alla ricorsione qui, ma al momento non riesco a pensare ad alcun altro esempio carino e poco chiaro.

Answer 3

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

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

La crescita raddoppia con ogni addizione al set di dati di input. La curva di crescita di una funzione O (2N) è esponenziale: inizia in modo molto superficiale, quindi aumenta in modo meteorologico. Il mio esempio di grande O (2^n), ma molto meglio è questo:

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

In questo programma metodo di stampe tutte le mosse per risolvere "Torre di Hanoi" problema. Entrambi gli esempi utilizzano ricorsivamente per risolvere il problema e hanno un tempo di esecuzione O (2^n) grande.

Answer 4

c^n = tutte le combinazioni di elementi n da un alfabeto di dimensioni c.

In particolare, 2^N è tutti i numeri rappresentabili con N bit.

I casi più comuni sono implementati in modo ricorsivo, qualcosa di simile:

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