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

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

Знаете ли вы, почему доступ по индексу константный, и понимаете ли, как это выглядит в Kotlin и Java на Android. Следом обычно спрашивают про разницу ArrayList и LinkedList, про IntArray против Array<Int> или про то, какой список лежит под адаптером RecyclerView.

Как отвечать

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

Дальше то, что показывает знание платформы:

• IntArray и Array<Int>: первый компилируется в int[], числа лежат подряд. Второй это Integer[], массив ссылок на упакованные объекты в куче. Индекс по-прежнему O(1), но после него идёт переход по ссылке, лишняя память и нагрузка на сборщик мусора;
• ArrayList.get(i): O(1), внутри обычный массив. Такие списки помечены интерфейсом RandomAccess;
• LinkedList.get(i): O(n), список идёт к элементу от ближайшего конца. Цикл по индексам от 0 до size по такому списку даёт O(n²);
• SparseArray: get(key) работает бинарным поиском по отсортированным ключам, это O(log n), а valueAt(index) и keyAt(index) берут элемент напрямую за O(1);
• проверка границ: выход за пределы бросает ArrayIndexOutOfBoundsException, у списков IndexOutOfBoundsException. Компилятор ART убирает проверки там, где индекс заведомо в пределах.

Практическая связка: onBindViewHolder получает позицию и на каждом скролле берёт элемент по индексу. Под адаптером обычно ArrayList или список, переданный в ListAdapter, и доступ по позиции там константный.

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

Говорят «у любого List доступ по индексу O(1)». List это интерфейс, и сложность зависит от реализации.

Путают доступ по индексу с поиском по значению. indexOf и contains у массива и ArrayList проходят по всем элементам, это O(n).

Не видят упаковки в Array<Int> и List<Int>. Для десятка элементов это неважно, а в горячем коде вроде обработки кадров или отрисовки на Canvas лишние объекты дают паузы сборщика мусора и пропущенные кадры.