Ответ
Удаление первого элемента из Go-слайса с помощью операции реслайсинга (s = s[1:]) является O(1) по времени выполнения самой операции. Это происходит за счёт простого смещения указателя начала среза на следующий элемент, без копирования данных.
s := []int{1, 2, 3, 4}
s = s[1:] // s теперь [2, 3, 4]Важные нюансы и ограничения:
- Память не освобождается немедленно: Исходный базовый массив, на который ссылался срез, остаётся в памяти. Если на него нет других ссылок, он будет очищен сборщиком мусора, но не сразу. Это может привести к "утечке памяти" (memory leak) в сценариях, где вы постоянно укорачиваете срез, но сохраняете ссылку на его старую, большую версию, или если базовый массив очень большой и его часть больше не нужна.
- O(1) только для операции: Если требуется фактическое удаление элемента с освобождением памяти и уменьшением базового массива (например, для предотвращения утечек или уменьшения потребления памяти), это потребует копирования оставшихся элементов в новый, меньший срез, что делает операцию O(N). Пример:
// O(N) операция для удаления первого элемента с потенциальным освобождением памяти s := []int{1, 2, 3, 4} newS := make([]int, 0, len(s)-1) // Создаем новый срез с меньшей емкостью newS = append(newS, s[1:]...) // Копируем все элементы, кроме первого s = newS // s теперь [2, 3, 4], старый базовый массив может быть GC'd - Альтернатива для истинного O(1) удаления: Для сценариев, где частые операции добавления/удаления из начала или конца коллекции должны быть истинно O(1) (включая управление памятью), лучше использовать структуры данных, такие как двусвязный список (
container/list).