big-oを使用した時間複雑度解析

Question

修正後、時間複雑度は実際にはO（2^n）であると結論付けました。

質問は時間の複雑さとは何ですか？それはO（2^n）か？

私はこれがforループのためだと思う理由は、n回runnedとみなされます。ネストされたwhileループは2^n回実行されます。 2番目のwhileループは2^n回実行されます。

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

編集：解析を分解したい場合は、以下のようにコメントしてください。

Answer 1

n個の要素のうちのT個の要素について、サブセットの総数は2^nです。これらの部分集合をすべてQに収めたければ、時間の複雑さは少なくともO（2^n）です。

---

実際、私はO（2^n）が答えだと思います。

私はあなたのアルゴリズムを正しく理解していれば、T内の各要素a_iを実行しようとしています.S中のすべての要素を取り除いてから、Sに2回戻します - a_iなしでa_iで1回。

したがって、時間の複雑さの合計は、（1 + 2 + 4 + ... + 2^n）回Cであり、Cはポップ、エンキュー、デキュー、プッシュする時間を表します。上記の項は2 ^（n + 1）-1に等しく、O（2^n）である。