Quelle est la complexité temporelle de l'opération d'insertion d'un élément dans une liste?

Временная сложность операции вставки элемента в список зависит от типа списка:

• Массив (например, std::vector в C++): вставка в конец — амортизированная O(1), вставка в середину или начало — O(n), так как нужно сдвигать элементы.
• Связный список (например, std::list в C++): вставка в произвольное место, если есть указатель на позицию — O(1), так как просто меняются указатели. Если позиция определяется по индексу — O(n), так как нужно пройти по элементам.

Пример для std::list:

std::list<int> lst = {1, 2, 3};
auto it = lst.begin();
std::advance(it, 1); // переходим ко второму элементу
lst.insert(it, 10); // вставляем 10 перед вторым элементом

Здесь вставка — O(1), так как итератор уже указывает на нужную позицию.