big-o - 使用 big-o 进行时间复杂度分析

Question

经过修改，我们得出结论，时间复杂度实际上是O(2^n)

问题是时间复杂度是多少？是 O(2^n) 还是？

我相信这是因为 for 循环被认为运行了 n 次。然后嵌套的 while 循环运行 2^n 次。第二个 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 两次 - 一次没有 a_i，一次有 a_i。

因此总时间复杂度是 (1+2+4+...+2^n) 乘以 C，C 代表弹出、入队、出队和推送的时间，即 O(1)。上面的项等于 2^(n+1)-1，它仍然是 O(2^n)。