Какова асимптотическая сложность основных операций со слайсами в Go?

Сложность операций со слайсами (динамическими массивами) в Go зависит от конкретной операции. Вот основные из них:

• 
  

  Доступ по индексу (slice[i]): O(1)
  
  Прямой доступ к элементу в памяти, не зависит от размера слайса.

  
  

• Добавление в конец (append):

  • Амортизированная сложность: O(1). В большинстве случаев, если в базовом массиве достаточно capacity, элемент просто добавляется в конец.
  • Худший случай: O(n). Если capacity исчерпана, Go выделяет память под новый, больший массив (обычно в 2 раза больше) и копирует в него все n старых элементов.
• 
  

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

  
  
• 
  

  Поиск элемента (линейный): O(n)
  
  В худшем случае необходимо проверить каждый элемент слайса, чтобы найти нужный.

  
  
• 
  

  Копирование слайса (copy): O(n)
  
  Сложность зависит от n — минимального из размеров исходного и целевого слайсов (n = min(len(src), len(dst))).

  
  

Пример роста capacity и сложности append:

s := make([]int, 0, 2) // len=0, cap=2
s = append(s, 1)       // O(1), len=1, cap=2
s = append(s, 2)       // O(1), len=2, cap=2

// Capacity исчерпана. Происходит реалокация.
s = append(s, 3)       // O(n), где n=2. Создается новый массив cap=4, 
                       // старые элементы копируются. len=3, cap=4