队列反转的渐近分析
Asymptotic Analysis of Reversing a Queue
void reverseQueue(queue<int>& Queue)
{
stack<int> Stack;
while (!Queue.empty())
{
Stack.push(Queue.front());
Queue.pop();
}
while (!Stack.empty())
{
Queue.push(Stack.top());
Stack.pop();
}
}
我想知道如果我们用 n 个元素的队列调用这个函数，它的 Big-O 或 Big-Theta 表示法是什么。它会不会是 O(n^2) 的东西，因为我们推入和弹出 n 个元素两次，以便以相反的顺序将它从堆栈移回队列？感谢您的帮助。
此函数的大 O 是 O(n)，因为您只遍历队列两次。从理论上讲，如果你执行 K 次，这也是正确的，其中 K 是一个常数，它不会随着队列大小 n 的变化而变化。 O(n^2) 是指，例如，您在另一个循环中有一个循环，因此您要遍历队列 n*n 次。
您还可以查看：
Which algorithm is faster O(N) or O(2N)?
void reverseQueue(queue<int>& Queue)
{
stack<int> Stack;
while (!Queue.empty())
{
Stack.push(Queue.front());
Queue.pop();
}
while (!Stack.empty())
{
Queue.push(Stack.top());
Stack.pop();
}
}
我想知道如果我们用 n 个元素的队列调用这个函数，它的 Big-O 或 Big-Theta 表示法是什么。它会不会是 O(n^2) 的东西，因为我们推入和弹出 n 个元素两次，以便以相反的顺序将它从堆栈移回队列？感谢您的帮助。
此函数的大 O 是 O(n)，因为您只遍历队列两次。从理论上讲，如果你执行 K 次，这也是正确的，其中 K 是一个常数，它不会随着队列大小 n 的变化而变化。 O(n^2) 是指，例如，您在另一个循环中有一个循环，因此您要遍历队列 n*n 次。
您还可以查看： Which algorithm is faster O(N) or O(2N)?