Можно ли решить задачу быстрее чем за линейное время

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

Умеете ли вы отличить задачу, где линейное время это нижняя граница, от задачи, где его можно побить за счёт свойств данных или предобработки. Обычно вопрос звучит после того, как вы решили задачу за O(n) на лайвкодинге: «а быстрее можно?».

Как отвечать

Начните с условия. Если ответ зависит от каждого элемента неупорядоченного входа (максимум, сумма, есть ли дубль), быстрее O(n) нельзя: непросмотренный элемент мог оказаться тем самым. Сублинейное время появляется, когда у данных есть структура:

• отсортированность: бинарный поиск за O(log n), в Python это bisect.bisect_left. Сюда же поиск первого True по монотонному условию;
• хэш-таблица: x in set и доступ к dict за O(1) в среднем, против O(n) для x in list. В худшем случае при коллизиях тоже O(n);
• предобработка: префиксные суммы строятся за O(n), а сумма любого отрезка потом считается за O(1). Для запросов с изменениями есть дерево отрезков или дерево Фенвика, O(log n) на операцию;
• формула: сумма от 1 до n это n * (n + 1) // 2, цикл не нужен;
• поддерживаемая структура: минимум в куче heapq лежит в heap[0] и достаётся за O(1).

Важная оговорка: если данные надо сначала прочитать или отсортировать, общая сложность не станет меньше O(n) или O(n log n). Выигрыш появляется на многих запросах к одним и тем же данным.

Полезно знать цену операций Python: len() за O(1), срез копирует и стоит O(k), list.insert(0, x) и list.pop(0) линейные, для очереди нужен collections.deque. bisect.insort находит место за O(log n), но вставка в список всё равно O(n).

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

Отвечают «нельзя, надо же посмотреть все элементы», не спросив, отсортированы ли данные и сколько будет запросов.

Предлагают отсортировать и сделать бинарный поиск ради одного запроса. Сортировка стоит O(n log n), это хуже линейного прохода.

Считают in одинаково быстрым для любой коллекции. Для списка это линейный поиск, и в цикле он превращает решение в O(n²).