Quale sarà la complessità di questo codice?

Question

Il mio codice è:

vector<int> permutation(N); 
vector<int> used(N,0); 

void try(int which, int what) { 
    // try taking the number "what" as the "which"-th element 
    permutation[which] = what; 
    used[what] = 1; 

    if (which == N-1) 
    outputPermutation(); 
    else 
    // try all possibilities for the next element 
    for (int next=0; next<N; next++) 
    if (!used[next]) 
    try(which+1, next); 

    used[what] = 0; 
} 

int main() { 
    // try all possibilities for the first element 
    for (int first=0; first<N; first++) 
    try(0,first); 
} 

stavo imparando la complessità da qualche sito web in cui mi sono imbattuto in questo codice. Secondo la mia comprensione, la riga seguente fa scorrere N volte. Quindi la complessità è O (N).

for (int first=0; first<N; first++) 

Avanti Sto considerando la chiamata ricorsiva.

for (int next=0; next<N; next++) 
    if (!used[next]) 
    try(which+1, next); 

Così, questa chiamata ricorsiva è il numero di step coinvolti = T (n) = Nc + t (0). (Dove è un certo passo costante) Non possiamo dire che per questo passo, la complessità è = O (N).

Così la complessità totale è - O (N.N) = O (N^2)

è la mia comprensione giusto? Grazie!

Answer 1

La complessità di questo algoritmo è O (N!) (O anche O (N! * N) se outputPermutation richiede O (N) che sembra possibile).

Questo algoritmo emette tutte le permutazioni dei numeri naturali 0..N senza ripetizioni.

funzione ricorsiva try si cerca di mettere in sequenza N elementi in posizione which e per ogni prova essa si richiama ricorsivamente per il prossimo which posizione, finché raggiunge which N-1. Inoltre, per ogni iterazione viene effettivamente invocato il tempo try (N - which), perché su ogni livello un elemento è contrassegnato come used per eliminare le ripetizioni. Quindi l'algoritmo prende N * (N - 1) * (N - 2) ... 1 passi.

Answer 2

È una funzione ricorsiva. La funzione "try" si chiama in modo ricorsivo, quindi c'è un ciclo in main(), un ciclo in try(), un ciclo nella chiamata ricorsiva a try(), un ciclo nella successiva chiamata ricorsiva a try() e così via sopra.

È necessario analizzare molto attentamente ciò che fa questa funzione, o si otterrà un risultato completamente sbagliato (come hai fatto tu). Potresti considerare di eseguire questo codice, con valori da N = 1 a 20 e misurare il tempo. Vedrai che non è assolutamente O (N^2). In realtà, non saltare nessuno dei valori di N; vedrai perché.