Очередь на обычном list: во что превращается pop(0) на 200 тысячах элементов
Коллега реализовал очередь на обычном списке и жалуется, что на 200 тысячах элементов код думает несколько секунд.
queue = list(range(200_000))
result = []
while queue:
result.append(queue.pop(0))
Какая у этого цикла асимптотика по времени и почему?
- O(n): каждый элемент попадает в result ровно один раз, значит работы линейно
- O(n log n): pop(0) внутри переиндексирует список за логарифм
- O(n^2): pop(0) удаляет из начала и сдвигает все оставшиеся элементы влево
- O(n), но с большой константой: list и deque отличаются только константой