Dinamik massiv tipli vektorə element əlavə etmə əməliyyatının ən pis və orta halda vaxt mürəkkəbliyi nədir?

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

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

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