Comment évaluer la complexité temporelle de l'opération d'ajout d'un élément à la fin d'un tableau de type Slice?

Добавление элемента в конец среза (slice) в Go обычно имеет амортизированную временную сложность O(1). Это связано с тем, что срезы имеют внутренний массив с определённой ёмкостью. Если при добавлении элемента ёмкость не превышена, операция просто добавляет элемент и занимает константное время.

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

Таким образом, в среднем (амортизированно) добавление элемента — O(1), но в худшем случае — O(n).