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

Доступ к элементу слайса по индексу имеет константную асимптотическую сложность — O(1).

Почему O(1)?

Слайс в Go — это легковесная структура (дескриптор), которая содержит три поля:

1. Указатель на начало базового массива (backing array).
2. Длину (len).
3. Ёмкость (cap).

Когда вы обращаетесь к элементу s[i], Go выполняет простое арифметическое вычисление адреса в памяти: адрес_начала_массива + i * размер_элемента. Эта операция занимает постоянное время, независимо от размера слайса.

Пример:

s := []int{10, 20, 30, 40, 50}

// Этот доступ занимает одинаковое время, 
// независимо от того, 5 элементов в слайсе или 5 миллионов.
val := s[2] // O(1)

Важные аспекты:

• Доступ по индексу vs. Итерация: Не путайте доступ по индексу (O(1)) с итерацией по всему слайсу (for range s), сложность которой линейна — O(n).
• Выход за границы: Попытка доступа к элементу по индексу >= len(s) вызовет panic.
• Стоимость роста: Операция append в среднем имеет амортизированную сложность O(1), но если ёмкость исчерпана, происходит выделение нового, большего массива и копирование всех элементов, что временно даёт сложность O(n).