Wie ist die zeitliche Komplexität der Operation zum Einfügen eines Elements in einen dynamischen Vektor im schlimmsten und durchschnittlichen Fall?

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

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

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