Какова временная сложность извлечения элементов из списка в Python?
Интересно, какова временная сложность метода pop для объектов списка в Python (в частности, в CPython). Также влияет ли значение N для list.pop (N) на сложность?
Ответы 4
Pop() для последнего элемента должен быть O (1), поскольку вам нужно только вернуть элемент, на который ссылается последний элемент в массиве, и обновить индекс последнего элемента. Я ожидаю, что pop() для произвольного элемента будет O (N) и потребует в среднем N / 2 операций, поскольку вам нужно будет переместить любые элементы за пределы элемента, который вы удаляете, на одну позицию вверх в массиве указателей.
@ntg список - это массив указателей. чтобы удалить указатель из массива в середине, все указатели, следующие за ним, должны быть перемещены в массиве за время, пропорциональное размеру списка (который мы обозначаем как N), таким образом, равняется O (N) . Чтобы уточнить, что N в нотации Big-O НЕ является индексом возвращаемого элемента, а является функцией, ограничивающей время работы алгоритма, при этом O (1) является постоянным временем, т. Е. Не зависит от размера список. O (N) означает, что ограничивающая функция является некоторой константой, умноженной на размер списка, f (n) = c * n + b.
Я поправляюсь :) Действительно, реализация списка представляет собой массив указателей. Итак, ваш ответ правильный. Под pop (N) в вашем ответе вы имеете в виду pop (k), N, где k - позиция удаляемого элемента, а размер указанного массива равен N. Тогда k может варьироваться от 0 до N-1, то есть на среднее N / 2 операции для перемещения элементов k + 1, ...., N-1 на одну позицию назад.
@ntg pop (0) - это O (N), а не O (1)
@BillYang Извиняюсь, я исправился. Я думал о классической реализации связанного списка (например, en.wikipedia.org/wiki/Linked_list) Однако список python, похоже, в основном представляет собой массив указателей ...
Да, это O (1), чтобы вытолкнуть элемент последний списка Python, и O (N), чтобы вытолкнуть элемент произвольный (поскольку весь остальной список должен быть сдвинут).
Вот отличная статья о том, как списки Python хранятся и управляются: http://effbot.org/zone/python-list.htm
Чтобы было понятно, list.pop (0) - это O (n), а list.pop () - это O (1).
И чтобы получить обе операции в O (1), используйте collections.deque см. здесь
@galath: для ясности, deque - это не O (1) для удаления произвольного элемента (вы не указали, что явно,, я просто хотел убедиться в отсутствии недоразумений), поскольку это двусвязный список блоков (т.е. массивы ), а не отдельные элементы. Следовательно, это все еще обычно O (n). Удаление первого элемента в двухсторонней очереди - O (1), так как у блока есть начальный и конечный индексы, которыми можно манипулировать, не перемещая элемент s вокруг.
@paxdiablo Извините, что не стал более явным. deque.pop не принимает аргумент документы на deque, как метод pop из списков. Удаляет крайний правый элемент.
Краткий ответ смотрите здесь: https://wiki.python.org/moin/TimeComplexity
Без аргументов, чтобы вытолкнуть его O (1)
С аргументом поп:
- Среднее время Сложность O (k) (k представляет число, переданное как аргумент в пользу поп-музыки
- Амортизированная временная сложность наихудшего случая O (k)
- Временная сложность наихудшего случая O (n)
Средняя временная сложность:
Каждый раз, когда вы вводите значение, временная сложность этой операции равна О (п - к).
Например, если у вас есть список из 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).
Вот что я написал, чтобы обдумать это на случай, если это поможет:
Это должно быть 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
Я согласен с приведенным ответом, но объяснение имхо неверно. Вы можете удалить любой объект из списка за время O (1) (по сути, сделайте указатель предыдущей точки на следующий и удалите это). Проблема в том, что для НАЙТИ объекта в этой позиции вам необходимо пройти по списку до этой позиции. point (занимает время O (N), усреднение не требуется). Наконец, особое примечание: pop (0) будет принимать O (1), а не O (0).