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

Сложность добавления элемента в конец слайса с помощью встроенной функции append — амортизированная O(1).

Это означает, что средняя стоимость операции стремится к константе. Рассмотрим два сценария:

1. 
   

   Когда capacity слайса достаточна (len < cap): Происходит простая вставка элемента в следующую свободную ячейку. Это очень быстрая операция со сложностью O(1).

   
   

2. Когда capacity исчерпана (len == cap): Происходит более дорогая операция:

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

Благодаря стратегии удвоения capacity, дорогостоящие операции O(n) происходят всё реже по мере роста слайса, поэтому средняя (амортизированная) стоимость остается O(1).

package main

import "fmt"

func main() {
    s := make([]int, 0, 3) // len=0, cap=3
    s = append(s, 1, 2, 3) // Три операции O(1)
    fmt.Printf("len=%d, cap=%d, data=%vn", len(s), cap(s), s)

    // Сейчас len == cap, следующий append вызовет реаллокацию
    s = append(s, 4) // Операция O(n), где n=3
    fmt.Printf("len=%d, cap=%d, data=%vn", len(s), cap(s), s)
}