使用big-o进行时间复杂度分析
使用big-o进行时间复杂度分析
提问于 2016-02-23 08:03:06
经过修改，我们得出的结论是时间复杂度实际上是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);
}
}
} 编辑:如果你想让我分解分析，请在下面发表评论。
回答 1
Stack Overflow用户
发布于 2016-02-23 08:23:11
对于包含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)。
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://stackoverflow.com/questions/35566366
复制相关文章
相似问题
腾讯云开发者
