使用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)。