Какова сложность операции добавления элемента в список?

Чтобы ответить на этот вопрос, нужно разобраться, как списки устроены на низком уровне. Определение списка в исходниках CPython выглядит так:

typedef struct {
PyObject_VAR_HEAD
PyObject **ob_item;
Py_ssize_t allocated;
} PyListObject;

Здесь ob_item -- это непрерывный массив указателей на элементы списка, а allocated содержит длину массива. Вот и все, что нужно знать, чтобы отвечать на вопросы о сложности операций со списками.

Во-первых, отсюда сразу видно, что получить длину массива можно очень быстро, за O(1), потому что не нужно пересчитывать все элементы.

len(a) # O(1)

Ещё сразу понятно, что при такой реализации стоимость индексирования не зависит от длины списка или значения индекса, так как изменить значение по известному номеру ячейки тоже можно тоже за O(1).

a[10] = 5 # O(1)

А вот чтобы найти значение в списке, придется обходить каждую ссылку и проверять содержимое на равенство. Поэтому проверить вхождение -- операция дорогая, в худшем случае O(n).

5 in a # O(n)

Добавление одиночных элементов в конец списка (метод append()) в большинстве случаев работает за O(1). Но здесь есть одна деталь: место в памяти для массива указателей аллоцируется заранее. И когда занятый объем памяти истощается, интерпретатор выделяет ещё примерно 15% от объема массива. Эта периодическая экспансия время от времени несколько замедляет добавление новых элементов в список, поэтому об O(1) можно говорить условно.

a.append(5) # ~O(1)

Еще одна распространенная потребность это конкатенировать списки, например, с помощью оператора +. Сложность конкатенации линейно зависит от длины присоединяемого списка: если его длина 100 элементов, то нужно 100 раз добавить в конец новый элемент.

a + b # ~O(k)

Чтобы получить доступ к элементам слайса a[i:j], нужно итерироваться между индексами i и j. Поэтому сложность такой операции O(k), где k -- длина слайса. А вот удалить слайс это O(n), из-за необходимости сдвинуть все следующие за удаленным участком элементы на новые места, здесь n -- длина всего массива.

a[i:j] # ~O(k)
del a[i:j] # ~O(n)

Метод, который получает и удаляет последний элемента списка pop(), имеет сложность O(1), в то время как pop(i) элемента из середины списка требует O(n). Почему так? Потому что после того, как один указатель был удален из середины или начала, нужно передвинуть все следующие за ним на 1 позицию вперёд. А когда элемент был удален из конца массива, этого делать не нужно. По этой же причине вычленение по индексу(pop) или вставка элемента в середину списка тоже дорогая операция и требует O(n) операций.

a.pop() #O(1)
a.pop(i) #O(n)
a.insert(i, item) #O(n)

Обобщим:

Операция Сложность
----------------------
len(a) O(1)
a[i] O(1)
a[10] = 5 O(1)
5 in a O(n)
a.append(5) ~O(1)
a + b O(k)
a[i:j] O(k)
del a[i:j] O(n)
a.pop() O(1)
a.pop(i) O(n)
a.insert(i, item) O(n)

В общем, чтобы отвечать на вопросы о сложности операций со списками, нужно понимать, как они устроены на низком уровне. Самые дорогие операции -- те, которые требуют обхода части или всего списка, например, поиск значения в списке, конкатенация, слайсинг, удаление или добавление элементов в начало списка. Самые экономные операции -- получение длины списка, операции с элементами в конце списка и со значениями по известному индексу.

В общем случае, сложность добавления элемента в список зависит от того, в середину массива мы добавляем элемент или в конец. Добавить элемент в начало или середину списка это O(n), но операция append() требует только O(1)🐍