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

Сложность удаления элемента из slice зависит от его позиции:

1. Удаление из середины или начала: O(n)

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

// Удаление элемента по индексу i
func remove(s []int, i int) []int {
    // s[i+1:]... копирует все элементы после i
    // на место начиная с i
    return append(s[:i], s[i+1:]...)
}

2. Удаление последнего элемента: O(1)

Это самый быстрый случай, так как не требует перемещения элементов. Сложность — O(1).

// Удаление последнего элемента
s = s[:len(s)-1]

3. Удаление без сохранения порядка: O(1)

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

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