Analisi della complessità del tempo usando big-o

Question

Dopo la revisione, abbiamo concluso che la complessità temporale è in realtà O (2^n)

La domanda è qual è la complessità del tempo? O (2^n) o?

La ragione per cui ritengo che ciò sia dovuto al ciclo for è considerata eseguita all'ora. Quindi il ciclo while annidato viene eseguito 2^n volta. Il secondo ciclo while viene eseguito 2^n volta.

Algorithm subsetsGenerator(T)  
Input: A set T of n elements  
Output: All the subsets of T stored in a queue Q {  

create an empty queue Q;  
create an empty stack S;  
let a1, a2, …, an be all the elements in T;  
S.push({}); // Push the empty subset into the stack  
S.push({a1})   
for (each element ai in T-{a1})   
{ 
    while (S is not empty)     
    { 
x=S.pop;      
Q.enqueue(x);       
x=x ∪ { ai };      
Q.enqueue(x);      
    }    

if (ai is not the last element)     
    while (Q is not empty)      
    { 
    x=Q.dequeue();       
    S.push(x);       
    }   
}  
} 

Modifica: Se vuoi che analizzi l'analisi, commenta qui sotto.

Answer 1

Per il set T di n elementi, il numero totale di sottoinsiemi è 2^n. Se si desidera mantenere tutti questi sottoinsiemi in Q, la complessità temporale è almeno O (2^n).

---

In realtà penso che O (2^n) sia la risposta.

Se capisco correttamente il tuo algoritmo, stai provando a fare per ogni elemento a_i in T, estrai tutto in S, rimettilo in S due volte - una volta senza a_i e una volta con a_i.

Quindi la complessità del tempo totale è (1 + 2 + 4 + ... + 2^n) volte C, C sta per il tempo di pop, accodamento, dequeue e push, che è O (1). Il termine precedente è uguale a 2^(n + 1) -1 che è ancora O (2^n).