Асимптотический анализ обращения очереди

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();
         }
    }

Мне было интересно, что бы обозначения Big-O или Big-Theta этой функции были бы, если бы мы назвали ее с очередью из n элементов.Будет ли это что-то вроде O (n ^ 2), так как мы дважды нажимаем и выталкиваем n элементов, чтобы переместить их из стека обратно в очередь в обратном порядке?Спасибо за любую помощь.

Answer 1

Большой O для этой функции - O (n), потому что вы пересекаете очередь только дважды.Теоретически это также верно, если вы делаете это K раз, где K - постоянная величина, и она не изменяется с размером очереди n.O (n ^ 2) - это когда, например, у вас есть цикл внутри другого, и вы пересекаете очередь n * n раз.

Вы также можете проверить: Какой алгоритм быстрее O(N) или O (2N)?