Временная сложность pop с аргументом в python? [Дубликат]

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

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

Ниже приведен короткий ответ: https://wiki.python.org/moin/TimeComplexity

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

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

• Среднее время Сложность O (k) (k представляет число, переданное в качестве аргумента для pop
• Амортизированное наихудшее временное время сложность O (k)
• Худшая временная сложность O (n)

Средняя временная сложность:

• Каждый раз, когда вы вводите значение временной сложности этой операции - O (n - k).
• Например, если у вас есть список из 9 элементов, кроме удаления из конца списка, это 9 операций и удаление с самого начала из списка - 1 операция (удаление 0-го индекса и перемещение всех остальных элементов в их текущий индекс - 1)
• Так как n - k для среднего элемента списка - это k операций, среднее может быть сокращено к O (k).
• Другой способ подумать об этом заключается в том, что представьте, что каждый индекс был удален из вашего списка из 9 элементов один раз. f 45 операций. (9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45)
• 45 равно O (nk), и поскольку поп-операция произошла 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).

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

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