#python
Вопрос:
Интересно, какова временная сложность метода pop для объектов списка в Python (в частности, в CPython). Также влияет ли значение N для list.pop(N) на сложность?
Ответ №1:
Да, это O(1), чтобы вставить последний элемент списка Python, и O(N), чтобы вставить произвольный элемент (так как вся остальная часть списка должна быть сдвинута).
Вот отличная статья о том, как хранятся и обрабатываются списки Python: http://effbot.org/zone/python-list.htm
Комментарии:
1. Поэтому, чтобы было ясно, list.pop(0) — это O(n), а list.pop () — O(1).
2. И чтобы получить обе операции в O(1), используйте коллекции. деке смотри здесь
3. @galath: просто для ясности,
dequeэто не O(1) для удаления произвольного элемента (вы не указали это явно, я просто хотел убедиться в отсутствии недоразумений), так как это двусвязный список блоков (т. Е. массивов ), а не отдельных элементов. Следовательно, это все еще, как правило, O(n). Удаление первого элемента в деке равно O(1), так как блок имеет начальный и конечный индексы, которыми можно управлять, не перемещая элемент s вокруг.4. @paxdiablo Извините, что не был более откровенен.
deque.popне принимает аргумент docs в deque , напримерpopметод из списков. Он удаляет самый правый элемент.
Ответ №2:
Pop() для последнего элемента должно быть O(1), так как вам нужно только вернуть элемент, на который ссылается последний элемент в массиве, и обновить индекс последнего элемента. Я бы ожидал pop() , что произвольный элемент будет равен O(N) и потребует в среднем N/2 операций, поскольку вам нужно будет переместить любые элементы за пределы элемента, который вы удаляете, на одну позицию вверх в массиве указателей.
Комментарии:
1. Я согласен с данным ответом, но объяснение имхо неверно. Вы можете удалить любой объект из списка за O(1) раз (по сути, сделайте так, чтобы указатель prev указывал на следующий, и удалите это). Проблема в том, что для того, чтобы НАЙТИ объект в этой позиции, вам нужно пройти по списку до этой точки (требуется O(N) времени, усреднение не требуется.) Наконец, примечание для особого случая: pop(0) будет принимать O(1), а не O(0).
2. @ntg список представляет собой массив указателей. чтобы удалить указатель из массива в середине, все указатели, следующие за ним, должны быть перемещены вверх по массиву за время, пропорциональное размеру списка (который мы обозначаем как N), таким образом, равное O(N). Для уточнения N в обозначении Big-O НЕ является индексом возвращаемого элемента, а функцией, ограничивающей время выполнения алгоритма, при этом O(1) является постоянным временем, т. Е. Это не зависит от размера списка. O(N) означает, что ограничивающая функция в несколько раз больше размера списка, f(n) = c*n b.
3. Я исправляюсь 🙂 Действительно, реализация списка представляет собой массив указателей. Так что ваш ответ верен. Под pop(N) в своем ответе вы подразумеваете pop(k),N, где k-позиция удаляемого элемента, а размер указанного массива равен N. Тогда k может варьироваться от 0 до N-1, таким образом,в среднем N/2 операции для перемещения элементов k 1,…., N-1 на одну позицию назад.
4. @ntg pop(0) — это O(N), а не O(1)
5. @BillYang Приношу извинения, как уже было сказано, я исправляюсь. Я думал о классической реализации связанного списка (например en.wikipedia.org/wiki/Linked_list ) Однако список python, по-видимому, в основном представляет собой массив указателей…
Ответ №3:
Это должно быть O(1) с L. pop(-1) и O(n) с L. pop(0)
см. Следующий пример:
from timeit import timeit
if __name__ == "__main__":
L = range(100000)
print timeit("L.pop(0)", setup="from __main__ import L", number=10000)
L = range(100000)
print timeit("L.pop(-1)", setup="from __main__ import L", number=10000)
>>> 0.291752411828
>>> 0.00161794329896
Комментарии:
1. почему это происходит? каково почтение «Л. поп(0)» и
L.pop(-1)
Ответ №4:
Короткий ответ-посмотрите здесь: https://wiki.python.org/moin/TimeComplexity
Без аргументов, чтобы вставить его O(1)
С аргументом, чтобы поп:
- Средняя временная сложность O(k) (k представляет число, переданное в качестве аргумента для pop
- Амортизированная временная сложность наихудшего случая O(k)
- Наихудшая временная сложность O(n)
Средняя временная сложность:
- Каждый раз, когда вы вводите значение, временная сложность этой операции равна O(n — k).
- Например, если у вас есть список из 9 элементов, удаление из конца списка составляет 9 операций, а удаление из начала списка — 1 операция (удаление 0-го индекса и перемещение всех остальных элементов в их текущий индекс-1)
- Поскольку n — k для среднего элемента списка равно k операций, среднее значение может быть сокращено до O(k).
- Другой способ подумать об этом-представить, что каждый индекс был удален из вашего списка из 9 пунктов один раз. Это будет в общей сложности 45 операций. (9 8 7 6 5 4 3 2 1 = 45)
- 45 равно O(nk), и поскольку операция pop произошла O(n) раз, вы делите nk на n, чтобы получить O(k)
Амортизированная Временная Сложность В Наихудшем Случае
- Представьте, что у вас снова есть список из 9 пунктов. Представьте, что вы удаляете каждый элемент списка, и происходит наихудший случай, и вы каждый раз удаляете первый элемент списка.
- Поскольку список уменьшается на 1 каждый раз, общее количество операций уменьшается каждый раз с 9 до 1.
- 9 8 7 6 5 4 3 2 1 = 45. 45 равно O(nk). Поскольку вы выполнили 9 операций, а 9-это O(n) для расчета амортизированного наихудшего сценария, вы выполняете O(nk) / O(n), что равно O(k)
- Утверждение, что это O(n) для средней и амортизированной сложности времени наихудшего случая, также в некотором роде правильно. Обратите внимание, что O(k) приблизительно равно O(1/2 n), и удаление константы равно O(n)
Наихудшая Временная Сложность
- В отличие от амортизированной сложности времени наихудшего случая, вы не учитываете состояние структуры данных и просто думаете о наихудшем случае для любой отдельной операции.
- В этом случае в худшем случае вам придется удалить 1-й элемент из списка, который составляет O(n) раз.
Вот что я написал, чтобы обдумать это на случай, если это поможет: