c++ - 队列反转的渐近分析

Question

    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 个元素两次，以便以相反的顺序将它从堆栈移回队列？感谢您的帮助。

Answer 1

此函数的大 O 是 O(n)，因为您只遍历队列两次。从理论上讲，如果你执行 K 次，这也是正确的，其中 K 是一个常数，它不会随着队列大小 n 的变化而变化。 O(n^2) 是指，例如，您在另一个循环中有一个循环，因此您要遍历队列 n*n 次。

您还可以检查: Which algorithm is faster O(N) or O(2N)?