Какова временная сложность выталкивания элементов из списка в Python?

Question

Интересно, какова временная сложность метода pop объектов списка в Python (в частности, в CPython). Также влияет значение N для list.pop (N) на сложность?

Answer 1

Да, это O (1), чтобы вытолкнуть последний элемент списка Python, и O (N), чтобы вытолкнуть произвольный элемент (так как весь остальной список должен быть сдвинут).

Вот отличная статья о том, как списки Python хранятся и обрабатываются: http://effbot.org/zone/python-list.htm

Answer 2

Pop() для последнего элемента должно быть O (1), поскольку вам нужно только вернуть элемент, указанный последним элементом в массиве, и обновить индекс последнего элемента. Я ожидал бы, что pop() для произвольного элемента будет O (N) и потребует в среднем N / 2 операций, поскольку вам нужно будет перемещать любые элементы за элемент, который вы удаляете, на одну позицию вверх в массиве указателей.

Answer 3

Краткий ответ смотрите здесь: https://wiki.python.org/moin/TimeComplexity

Без аргументов, чтобы вытолкнуть его O (1)

С аргументом для pop:

• Среднее время Сложность O (k) (k представляет число, переданное в виде аргумент для поп
• Амортизированная сложность времени наихудшего случая 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 / 2n), а падение постоянной равно O (n)

Наихудший случай сложности

• В отличие от амортизированной временной сложности в наихудшем случае вы не учитываете состояние структуры данных и просто думаете о худшем случае для любой отдельной операции.
• В этом случае наихудшим случаем является удаление 1-го элемента из списка, что является O (n) раз.

Вот что я должен обдумать, если это поможет:

Answer 4

Это должно быть 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