Можно ли найти решение быстрее, чем O(n^2)?

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

Это вопрос после первого решения на лайвкодинге: интервьюер смотрит, умеете ли вы найти узкое место и заменить вложенный цикл подходящей структурой данных. Следом обычно спрашивают, чем вы платите за ускорение, чаще всего памятью, и можно ли ещё быстрее.

Как отвечать

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

• хэш-таблица: внутренний поиск превращается в проверку в set или dict за O(1) в среднем. Классика: сумма двух чисел, дубликаты, подсчёт частот через collections.Counter. Итог O(n) по времени и O(n) по памяти;
• сортировка и два указателя: O(n log n) на сортировку плюс линейный проход. Годится, когда памяти мало или пары нужны по порядку;
• префиксные суммы и скользящее окно: суммы на отрезках и подмассивы с условием за O(n) вместо перебора всех отрезков;
• куча: топ-k элементов за O(n log k) через heapq, без полной сортировки;
• бинарный поиск: по отсортированным данным, в NumPy это np.searchsorted.

Для задач из анализа данных добавьте свой контекст. Попарные расстояния между n точками дают O(n²) по определению, поэтому для поиска ближайших соседей берут KD-дерево на малых размерностях или приближённый поиск (HNSW, FAISS). Соединение таблиц в pandas через merge работает по хэшу, а не вложенными циклами.

Честно назовите пределы: если ответ сам содержит все пары, быстрее O(n²) не выйдет, а сортировка сравнениями не бывает быстрее O(n log n).

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

Выдают векторизацию на NumPy за улучшение асимптотики. Код ускоряется в разы за счёт константы, но O(n²) остаётся O(n²), и с ростом данных это проявится.

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

Забывают посчитать сортировку. Решение «двумя указателями за O(n)» на неотсортированных данных на самом деле стоит O(n log n).