Можно ли получить данные из массива алгоритмом со сложностью O(1)

«Можно ли получить данные из массива алгоритмом со сложностью O(1)» — вопрос из категории Алгоритмы, который задают на 10% собеседований Frontend Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Ответ

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

const arr = [10, 20, 30, 40];
console.log(arr[2]); // 30 - доступ за O(1)

Однако поиск элемента по значению без дополнительных структур данных (например, хэш-таблицы) будет O(n), так как требуется перебор элементов.