Имеет ли вставка в конце списка временную сложность O (1)?

Есть ли разница между append и insert в конце списка? Является ли insert в конце списка операцией с постоянным временем?

nums = [1, 2, 3]
nums.append(4)  # Time complexity: O(1)
nums.insert(len(nums), 5)  # Time complexity: O(?)

Согласно статье TimeComplexity в Python Wiki, средний случай для append равен O (1) , а средний случай для insert - O (n). Однако в руководстве по Python упоминается что:

... и a.insert(len(a), x) эквивалентно a.append(x).

Я не уверен, что эквивалент означает эквивалент по функциональности или эквивалент по временной сложности. Кто-нибудь знает?


python list time-complexity cpython
person Flux    schedule 04.02.2020    source источник
comment
статья timecomplexity верна для общего случая, потому что insert не всегда находится в конце списка.   -  person Paritosh Singh    schedule 04.02.2020
comment
@ParitoshSingh Да, я знаю. Мой вопрос в том, является ли временная сложность для insert O (1) в особом случае вставки в конец списка.   -  person Flux    schedule 04.02.2020
comment
n во вставке - это фактически количество элементов, которые необходимо переместить. Если перемещать элементы не нужно, эту операцию можно проигнорировать. В любом случае это все равно будет временная сложность O (n) просто потому, что большая нотация O на самом деле не измеряет некоторую расплывчатую или даже точную временную сложность, это больше для описания того, как их требования к времени / пространству работы растут по мере увеличения размера ввода . Подробнее см. в Википедии.   -  person metatoaster    schedule 04.02.2020
comment
Другими словами, list.insert всегда в среднем O (n), и что нотация большого O не делает конкретной адресации крайних случаев (таких как лучший или худший сценарий; в вашем случае операционная, которая может быть уменьшена к простому list.append).   -  person metatoaster    schedule 04.02.2020
comment
Еще более педантично, append амортизируется за O (1), а не за O (1). См. эту ветку   -  person metatoaster    schedule 04.02.2020

Ответы (2)


arrow_upward
2
arrow_downward

Наихудшая временная сложность для вставки в список - O(n-i), где n - длина списка, а i - индекс, в который вы вставляете.

Так что, если вы вставляете последний индекс, получается O(1).

Вот статья, которая может помочь вам лучше понять:

https://yourbasic.org/algorithms/time-complexity-arrays/.

person Prashant Kumar    schedule 04.02.2020

arrow_upward
2
arrow_downward

Что касается эквивалентной функциональности, я бы сказал, что это правда, поскольку оба они будут давать одинаковые результаты для списков Python.

С точки зрения временной сложности это в значительной степени эквивалентно списку в таком случае, поскольку реализация списка insert() работает, сдвигая элементы за индексом, поэтому, если новый элемент вставлен в конец списка, операции сдвига не выполняются. Это можно проверить, просмотрев реализацию list insert / а>. В строке реализации вставки 248-251,

for (i = n; --i >= where; )
        items[i+1] = items[i];
Py_INCREF(v);
items[where] = v;

Между тем, при реализации list append

Py_INCREF(v);
PyList_SET_ITEM(self, n, v);

где PyList_SET_ITEM определяется как:

#define PyList_SET_ITEM(op, i, v) (((PyListObject *)(op))->ob_item[i] = (v))

Таким образом, поскольку where равно n, который в данном случае является размером списка, цикл for немедленно завершается. Несколько строк после этого в значительной степени эквивалентны, по сути, это просто вставка элемента в массив.

Следовательно, можно сказать, что для этого случая сложность амортизированного времени такая же, что составляет O (1)

person Hans Tananda    schedule 04.02.2020