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

Question

Есть ли разница между 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).

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

Answer 1

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

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

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

Между тем в списке реализации добавляется

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, что в данном случае является размером списка, значение для l oop сразу прекращается. Несколько строк после этого в значительной степени эквивалентны, то есть просто вставляют элемент в массив.

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

Answer 2

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

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

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

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