Очередь на двух стеках: почему дорогой pop не делает алгоритм квадратичным
class Queue:
def __init__(self):
self.inbox = []
self.outbox = []
def push(self, x):
self.inbox.append(x)
def pop(self):
if not self.outbox:
while self.inbox:
self.outbox.append(self.inbox.pop())
return self.outbox.pop()
Выполняется произвольная последовательность из n операций push и pop (каждый pop вызывается, когда очередь непуста). Что верно про суммарное время?
- Один pop в худшем случае стоит O(n), значит n операций дают O(n^2) — это и есть точная оценка
- Суммарно O(n): каждый элемент перекладывается из inbox в outbox ровно один раз
- Каждая операция O(1) в худшем случае: у списка pop() без индекса всегда константа, значит и у очереди
- Переливать inbox в outbox нужно на каждом pop, иначе нарушится порядок FIFO — отсюда и O(n^2)