Какая асимптотика у вставки элемента динамического массива?

Асимптотика вставки элемента в динамический массив (slice)

Асимптотика вставки элемента в динамический массив в Go зависит от конкретного места вставки и состояния массива. В Go динамический массив реализован через тип slice, поэтому рассмотрим его поведение.

1. Асимптотика в лучшем случае — O(1)

При вставке элемента в конец среза (append), когда capacity (ёмкость) превышает текущую длину, операция выполняется за константное время O(1). Элемент просто добавляется в следующую доступную позицию памяти.

slice := []int{1, 2, 3} // capacity >= len
slice = append(slice, 4) // O(1) - ёмкость достаточна

2. Асимптотика в худшем случае — O(n)

Если при append ёмкость среза недостаточна, происходит следующее:

• Создается новый массив с увеличенной ёмкостью (обычно удваивается или увеличивается по формуле cap*2 для маленьких срезов).
• Все существующие элементы копируются в новый массив.
• Затем добавляется новый элемент.

Копирование всех n элементов требует линейного времени O(n).

slice := []int{1} // capacity = 1, len = 1
slice = append(slice, 2) // Требуется расширение: O(n) копирование

3. Вставка в середину или начало — O(n)

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

// Вставка в начало
slice := []int{2, 3}
newSlice := []int{1}
newSlice = append(newSlice, slice...) // О(n) - копирование всех элементов

Или более явный пример вставки в середину:

func insertAt(slice []int, index int, value int) []int {
    // Создаём новый срез с дополнительным элементом
    newSlice := make([]int, len(slice)+1)
    // Копируем часть до индекса: O(k)
    copy(newSlice[:index], slice[:index])
    // Вставляем новый элемент
    newSlice[index] = value
    // Копируем часть после индекса: O(n-k)
    copy(newSlice[index+1:], slice[index:])
    return newSlice
}
// Общая асимптотика: O(n)

Амортизированная (средняя) асимптотика

Для операции append, даже с учетом периодических расширений, амортизированная сложность остается O(1). Это связано с тем, что дорогостоящие операции расширения и копирования происходят редко (при удвоении capacity), и их стоимость «распределяется» по множеству быстрых O(1) операций добавления.

Ключевые выводы для Go Developer:

• Основная операция append — амортизированно O(1), но может быть O(n) при расширениях.
• Вставка не в конец — всегда O(n) из- необходимости сдвига элементов.
• Рекомендации: Для частых вставок в середину/начало стоит рассмотреть другие структуры данных (например, двусвязные списки или структуры с более эффективной вставкой). Однако для большинства случаев в Go append в конец эффективен благодаря стратегии динамического увеличения ёмкости и амортизированной сложности.