В чем проблема решения с вложенным циклом за O(n^2)?

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

Умеете ли вы оценить, при каком объёме данных квадратичное решение перестаёт работать, и знаете ли стандартные способы уйти от него. В data-ml следом почти всегда спрашивают про векторизацию: как переписать то же на NumPy или pandas без питоновских циклов.

Как отвечать

Начните с цифр. При n = 10 000 вложенный цикл делает около 10^8 итераций, в чистом Python это секунды или минуты в зависимости от тела цикла. При n = 10^6 уже 10^12 операций, порядка суток. Удвоение данных умножает время на четыре, поэтому решение, которое летало на выборке, встаёт на полном датасете. Бывает и проблема памяти: попарная матрица расстояний на 100 000 объектов в float64 занимает около 80 ГБ.

Затем приёмы, которые убирают квадрат:

• хэш-таблица: поиск пары с заданной суммой, дубликатов, пересечений через set или dict за O(n);
• сортировка: O(n log n), дальше два указателя или бинарный поиск через bisect;
• префиксные суммы и скользящее окно: суммы подотрезков без повторного пересчёта;
• join вместо циклов: сопоставление двух таблиц через pd.merge по ключу, а не два вложенных for по строкам;
• поиск соседей: KDTree и BallTree в scikit-learn, на больших размерностях ANN-индексы вроде FAISS или HNSW.

Разведите асимптотику и константу. Векторизация не меняет O(n^2), но уносит цикл в C и ускоряет его на порядки, поэтому scipy.spatial.distance.cdist на нескольких тысячах точек вполне допустим. И скажите, когда квадрат приемлем: n ограничено сотнями, анализ разовый или задача по сути требует всех пар.

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

Говорят «квадрат это плохо» без оценки. Сильный ответ называет n, при котором решение перестаёт укладываться в лимит.

Считают df.apply векторизацией. Внутри это тот же питоновский цикл по строкам, а apply внутри apply даёт тот же O(n^2) с медленной константой.

Прячут квадрат в x in some_list внутри цикла. Проверка вхождения в список линейная, и безобидная строка превращает проход в O(n^2), а с set она стоит O(1) в среднем.