Какова асимптотическая сложность удаления элемента из слайса (slice) в Go?

Ответ

Сложность удаления элемента из слайса зависит от его позиции и от того, важен ли порядок оставшихся элементов.

Случай 1: Порядок элементов важен

Удаление из начала или середины: O(n). Чтобы сохранить порядок, все элементы справа от удаляемого необходимо сдвинуть на одну позицию влево. В худшем случае (удаление первого элемента) потребуется n-1 сдвигов.
```
// Удаление элемента по индексу с сохранением порядка
func remove(slice []int, i int) []int {
    return append(slice[:i], slice[i+1:]...)
}
```

Удаление с конца: O(1). Сдвигать элементы не нужно, достаточно просто уменьшить длину слайса.

// Удаление последнего элемента
func removeLast(slice []int) []int {
    if len(slice) == 0 {
        return slice
    }
    return slice[:len(slice)-1]
}

Случай 2: Порядок элементов не важен (оптимизация)

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

Техника: Элемент для удаления меняется местами с последним элементом в слайсе, после чего слайс усекается на один элемент.

// Удаление элемента по индексу за O(1) без сохранения порядка
func removeUnordered(slice []int, i int) []int {
    if len(slice) == 0 {
        return slice
    }
    // Заменяем удаляемый элемент последним
    slice[i] = slice[len(slice)-1]
    // Усекаем слайс
    return slice[:len(slice)-1]
}

Этот подход значительно эффективнее, если сохранение исходного порядка не является требованием.