Перейти к основному содержимому

Сложность операций со слайсами в Go

Слайс — это обертка над массивом. Операции с ним очень эффективны, если понимать, как они работают внутри.

1. Доступ по индексу (s[i])​

  • Сложность: $O(1)$ (Константная)
  • Почему: Процессор просто берет указатель на начало массива и прибавляет к нему смещение (индекс * размер_типа). Это мгновенная операция.

2. Append (Добавление в конец)​

Здесь есть важный нюанс — наличие свободной емкости (cap).

  • Лучший случай: $O(1)$ (константная). Если есть свободная емкость, Go просто записывает значение в следующую ячейку массива и инкрементирует len.
  • Худший случай: $O(n)$ (логарифмическая). Если свободного места нет (len == cap), происходит реаллокация: выделяется новая память и все $n$ элементов копируются в новый массив.
  • Амортизированная сложность: $O(1)$. Поскольку Go увеличивает емкость не на 1, а экспоненциально (обычно в 2 раза для малых слайсов), "дорогое" копирование происходит редко. В среднем за $n$ операций добавления сложность остается константной.

3. Удаление элемента (s = append(s[:i], s[i+1:]...))​

  • Сложность: $O(n - i)$ (логарифмическая), в среднем $O(n)$.
  • Почему: При удалении из середины или начала все элементы, стоящие после удаленного, должны быть сдвинуты влево на одну позицию, чтобы в массиве не осталось "дырки".

4. Вставка в середину​

  • Сложность: $O(n)$ (логарифмическая).
  • Почему: Аналогично удалению, нужно сдвинуть все элементы вправо, чтобы освободить место для нового элемента. Если при этом еще и превышена емкость, добавится операция копирования всего массива ($O(n)$) (логарифмическая).

5. Копирование слайса (copy(dst, src))​

  • Сложность: $O(n)$ (логарифмическая).
  • Почему: Нужно физически прочитать каждый байт из одного места и записать в другое. Чем больше элементов $n$, тем дольше процесс.

6. Поиск элемента (Unsorted)​

  • Сложность: $O(n) (логарифмическая)$.
  • Почему: В худшем случае (если элемент в самом конце или его нет) нам придется проверить каждый из $n$ элементов.

Итоговая таблица​

ОперацияСложностьПримечание
Доступ по индексу$O(1)$Самая быстрая операция
Append (в конец)$O(1)$ аморт.$O(n)$, если происходит реаллокация
Вставка (в начало/середину)$O(n)$Требует сдвига элементов
Удаление (из начала/середины)$O(n)$Требует сдвига элементов
Копирование (copy)$O(n)$Зависит от количества переносимых данных
Поиск (линейный)$O(n)$Проход циклом до нахождения

Совет для интервью:​

"В среднем (амортизировано) — $O(1)$, но в худшем случае, когда емкость исчерпана и требуется переаллокация, она составляет $O(n)$ из-за необходимости копирования всех существующих элементов в новую область памяти."