使用大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);                         
  }          
 }    
} 

编辑：如果您希望我分解这个分析，请在下面评论。

- Mikeez

---

你知道输出有多大吗？一个一个地向输出添加元素需要多长时间才能产生那么大的输出？你和你的朋友都分析错了。 - user2357112

是的，我们仍在考虑它，但我们正在使用一组4个元素进行分析。如果我们再次检查它，每个while循环都会给出2^n，而for循环只会给出n。 - Mikeez

这里有问题吗？ - Charlie

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

- bfrguci

---

我认为它是O(n(2^n))。我修改了我的分析。 - Mikeez

@Mikeez 虽然你正在使用 for 循环 n 次，但每次循环的规模并不相同 - 它是呈指数增长的。 - bfrguci

是的，你理解了我的算法，我应该解释得更清楚。基本上，它会取一个集合，最后输出所有子集。 - Mikeez

@Mikeez，我认为它的时间复杂度是O(2^n)。 - bfrguci

@Mikeez：“它正在获取一个集合，并且最终将输出所有子集。” - 我希望你有很多RAM（或非常小的集合）。 - aroth