Ответ
Добавление элемента в конец slice с помощью append имеет амортизированную сложность O(1).
Это означает, что в среднем операция выполняется за константное время. Однако, в худшем случае, когда внутренний массив (capacity) слайса переполнен, сложность становится O(n). В этот момент происходит:
- Выделение нового, большего по размеру массива.
- Копирование всех n элементов из старого массива в новый.
Go runtime использует стратегию роста, которая обеспечивает амортизированную сложность O(1). Для небольших слайсов capacity обычно удваивается, а для больших (более 1024 элементов) — увеличивается примерно в 1.25 раза. Из-за того, что дорогостоящие операции O(n) происходят редко, их стоимость "размазывается" по множеству быстрых O(1) вставок.
Пример:
// Создаем слайс с длиной 0 и емкостью 2
s := make([]int, 0, 2)
// len=1, cap=2. Сложность O(1)
s = append(s, 10)
// len=2, cap=2. Сложность O(1)
s = append(s, 20)
// len=3, cap=4. Происходит реаллокация.
// Создается новый массив (емкостью 4), копируются 2 элемента.
// Сложность O(n), где n=2.
s = append(s, 30)