Асимптотический анализ обращения очереди
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 элементов, чтобы переместить их из стека обратно в очередь в обратном порядке? Спасибо за любую помощь.
Решение
Big O для этой функции — O (n), потому что вы пересекаете очередь только дважды. Теоретически это также верно, если вы делаете это K раз, где K — постоянная величина, и она не изменяется с размером очереди n. O (n ^ 2) — это когда, например, у вас есть цикл внутри другого, и вы пересекаете очередь n * n раз.
Вы также можете проверить:
Какой алгоритм быстрее O (N) или O (2N)?
Другие решения
Других решений пока нет …
detector