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

Ответ 1

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

Ответ 2

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

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

Ответ 3

Короткий ответ - вот здесь: 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 элементов один раз. Это будет в общей сложности 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).

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