Что такое динамический массив и какова сложность вставки?

Динамический массив — это структура данных, которая автоматически изменяет свой размер при добавлении элементов, обычно увеличивая емкость в несколько раз, когда текущий размер заполнен.

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

Пример: в Go срезы (slice) реализованы на основе динамических массивов. При добавлении элементов с помощью append Go автоматически увеличивает емкость среза при необходимости.