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

Ответ

Сложность вставки элемента в начало или середину слайса — O(n), где n — количество элементов в слайсе.

Почему O(n)?
Это связано с тем, что для освобождения места под новый элемент необходимо сдвинуть все последующие элементы вправо. В худшем случае (вставка в начало, index = 0) потребуется сдвинуть все n элементов. Операция append, используемая для таких вставок, по сути создает новый слайс, копируя в него части старого и новый элемент.

Пример вставки в середину (на позицию i):

func insertIntoSlice(slice []int, index int, value int) []int {
    // Убедимся, что в capacity есть место для еще одного элемента
    if len(slice) == cap(slice) {
        // Реаллокация, если capacity исчерпан
    }
    // Расширяем слайс на один элемент (это O(1), если есть capacity)
    slice = append(slice, 0) 
    // Сдвигаем элементы вправо, чтобы освободить место
    copy(slice[index+1:], slice[index:])
    // Вставляем новый элемент
    slice[index] = value
    return slice
}

// Более идиоматичный, но менее наглядный способ:
func insertIdiomatic(slice []int, i int, value int) []int {
    return append(slice[:i], append([]int{value}, slice[i:]...)...)
}

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