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

Что проверяют

Базовое понимание, откуда берётся O(1), и знание того, как в Go устроены массивы и срезы. Почти всегда следом спрашивают про разницу между [N]T и []T, про сложность append или про индексацию строки.

Как отвечать

Доступ по индексу выполняется за O(1): элементы лежат в памяти подряд, и адрес i-го элемента равен адресу начала плюс i, умноженному на размер элемента. Одно умножение и одно сложение, независимо от длины.

Дальше специфика Go:

• массив [N]T: длина входит в тип, [3]int и [4]int это разные типы. Массив это значение, при присваивании и передаче в функцию он копируется целиком;
• срез []T: заголовок из трёх полей, указатель на базовый массив, len и cap. Доступ s[i] тоже O(1), добавляется одно разыменование указателя;
• проверка границ: рантайм проверяет индекс при каждом обращении, выход за пределы вызывает панику index out of range. Компилятор убирает лишние проверки, когда доказал, что индекс в пределах: например, после _ = s[3] обращения к индексам от 0 до 3 уже не проверяются;
• строки: s[i] возвращает байт, а не символ. Найти i-ю руну в строке UTF-8 можно только проходом с начала за O(n) либо заранее перевести строку в []rune.

Для контраста назовите, где индекса нет: container/list это двусвязный список, до нужного элемента идут перебором. У map доступ по ключу O(1) в среднем, но это хэш-таблица, а не адресная арифметика.

И оговорка про практику: O(1) не значит «одинаково быстро». Последовательный обход среза хорошо ложится на кэш процессора, а случайные обращения к большому срезу упираются в промахи кэша при той же асимптотике.

Где спотыкаются

Говорят, что срез заметно медленнее массива из-за накладных расходов. Разница в одной косвенности, а передача большого массива по значению с полным копированием обходится куда дороже.

Считают, что len(s) пересчитывает элементы. Длина хранится в заголовке среза и читается за O(1).

Путают доступ по индексу с append. Добавление в срез O(1) только амортизированно: когда cap исчерпан, рантайм выделяет новый массив большего размера и копирует элементы, а старые срезы продолжают смотреть на прежний массив.