Qual è la complessità temporale dell'operazione di inserimento di un elemento in un vettore dinamico nel caso peggiore e medio?

В динамическом массиве типа vector в C++ операция вставки элемента имеет:

• Среднюю временную сложность O(1) — когда есть свободное место в выделённой памяти, элемент просто добавляется в конец.
• Худшую временную сложность O(n) — когда выделённая память заполнена, происходит перераспределение (реаллоцирование) памяти: выделяется новый блок большего размера, все существующие элементы копируются в новый блок, и затем добавляется новый элемент.

Таким образом, несмотря на редкие дорогостоящие операции копирования, амортизированная сложность вставки остаётся O(1).