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

Асимптотическая сложность основных операций со слайсами в Go выглядит следующим образом:

• 
  

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

  
  
• 
  

  Получение длины (len(slice)): O(1).
  
  Длина хранится в заголовке слайса.

  
  
• 
  

  Создание подслайса (slice[a:b]): O(1).
  
  Эта операция создает только новый заголовок слайса (указатель, длина, емкость), который указывает на тот же базовый массив. Копирования элементов не происходит. Важно: это может привести к утечкам памяти, если маленький подслайс удерживает ссылку на огромный базовый массив.

  
  

• Добавление элемента (append): Амортизированная O(1).

  • Если cap > len: Сложность O(1). Новый элемент просто добавляется в свободное место в базовом массиве.
  • Если cap == len: Сложность O(n). Происходит реаллокация: создается новый, больший массив (обычно в 2 раза больше), и все n элементов из старого массива копируются в новый.
    
    За счет того, что реаллокации происходят редко, средняя (амортизированная) стоимость операции стремится к O(1).
• 
  

  Копирование (copy): O(k).
  
  Где k — минимальное из количеств элементов в исходном и целевом слайсах (k = min(len(src), len(dst))).

  
  
• 
  

  Итерация (for ... range): O(n).
  
  Требуется пройти по всем n элементам слайса.