O(1) - Константная Сложность

Проблема

В коде постоянно встречаются операции вроде «взять элемент по индексу» или «найти значение по ключу». Если не различать, какие из них правда не зависят от размера данных, а какие лишь выглядят простыми, легко ошибиться в оценке производительности целой системы. Разница между «эта операция быстрая всегда» и «эта операция быстрая, пока данных немного» решает, выдержит ли сервис рост в тысячу раз или начнёт тормозить уже на десятой тысяче записей.

Решение

Операция - O(1), если для неё существует фиксированное число шагов, которое не меняется, сколько бы данных ни было на входе. Узнать такой код просто: в нём нет циклов и нет обращений к структурам, которые сами зависят от размера данных - только прямой доступ по известному адресу, индексу или ключу. Внутри операции может быть несколько отдельных действий подряд (например, сравнение, потом присваивание), но их количество фиксировано заранее и не растёт вместе с n.

Как это работает

У O(1) есть точное определение: существует число c, такое что работа не превышает c, и это c не зависит от n вообще. У getElementAt это ровно 3 действия - проверка нижней границы, проверка верхней границы, чтение по адресу - и ни одно из них не становится длиннее с ростом массива. Это и делает функцию честным O(1), а не просто «выглядит быстрой на тестах».

Разница с O(n) видна на конкретных числах. Чтение arr[500] в массиве из 1 000 элементов - одна операция. То же чтение в массиве из 1 000 000 элементов - тоже одна операция: данные выросли в 1000 раз, а работа не выросла вовсе. Для сравнения, линейный поиск того же значения (материал O(n)) в худшем случае вырос бы вместе с массивом - с 1 000 сравнений до 1 000 000.

Прямой доступ по индексу работает за O(1) из-за того, как устроен массив в памяти: все его элементы лежат подряд, друг за другом, поэтому адрес любого элемента можно вычислить формулой начало + index * размер элемента, не заглядывая в предыдущие ячейки. У связного списка такой формулы нет - элементы разбросаны по памяти и связаны ссылками, поэтому доступ к n-му элементу там уже O(n), а не O(1).

Хеш-таблица (JS Map/Object, Python dict) добивается своего среднего O(1) иначе: ключ пропускается через хеш-функцию, которая превращает его в число - индекс внутри внутреннего массива - и дальше это уже обычный O(1)-доступ по индексу. «Средний случай» здесь важная оговорка: это работает, пока хеш-функция равномерно раскидывает ключи, без большого числа коллизий.

Частая ловушка - «амортизированный O(1)» путают с настоящим O(1). У push() в конец динамического массива (JS Array.push, растущий вектор в других языках) обычное добавление - O(1), но время от времени массиву не хватает места, и он копирует все элементы в новый, больший блок памяти - разовая операция O(n). Если размазать эти редкие O(n)-копирования по всем вызовам push, в среднем получается O(1) - но это не значит, что вообще каждый отдельный вызов гарантированно быстрый.

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

Нюансы выбора

Точечный доступ по известному адресу - индекс массива, ключ словаря, вершина стека. Если позиция или ключ заранее известны, ничего быстрее O(1) не построить.

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

Против O(log n) - если нужен не точный ключ, а диапазон значений («все заказы дороже $50»), хеш-таблица с её O(1) тут не поможет: для диапазонных запросов нужна упорядоченная структура вроде дерева, а значит и O(log n).

Не притворяться там, где неправда - если внутри «O(1)-операции» на самом деле прячется цикл или рекурсия по данным, это уже не O(1), и называть её так - ошибка, которая всплывёт при росте данных.

Примеры в коде

Хеш-таблицы CPython (dict) и V8 (Object/Map) - обе реализации построены вокруг того, чтобы чтение и запись по ключу оставались O(1) в среднем случае, даже при десятках миллионов записей.

Redis и Memcached - хранилища ключ-значение в оперативной памяти, где GET/SET по ключу спроектированы как O(1) - именно за счёт этого их используют как кэш перед медленной базой данных.

Хеш-индексы в базах данных (PostgreSQL hash index) - для точного совпадения по ключу дают O(1) доступ, в отличие от B-tree индекса того же движка, который для той же задачи работает за O(log n).

Массив с прямым доступом по индексу (в разделе сортировок используется в реализации каждого алгоритма) - наглядный пример того, откуда берётся O(1) в самом фундаменте: без него не работала бы ни одна из сортировок.

Когда применять

• Когда нужно достать значение по уже известному адресу, индексу или ключу - массив по индексу, объект/словарь по ключу, стек через push/pop.
• Когда операция выполняется очень часто (тысячи или миллионы раз в секунду) - именно там разница между O(1) и любым растущим классом становится решающей.

Примеры из практики

• JavaScript Map/Object и Python dict - чтение значения по ключу в среднем случае O(1), за счёт хеш-таблицы под капотом.
• Redis GET - классическое хранилище ключ-значение, спроектированное так, чтобы чтение по ключу оставалось O(1) даже при миллионах записей.