Какая асимптотическая сложность поиска в списке с вложенным циклом

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

Умеете ли вы оценить сложность по коду, а не по числу строк, и видите ли скрытые циклы. Для ML-позиции следом почти всегда просят ускорить: как найти пересечение двух списков на миллион элементов и как это сделать в pandas или NumPy.

Как отвечать

Базовый случай: два списка длиной n и m, для каждого элемента первого проходите второй. В худшем случае это n * m сравнений, сложность O(n·m), при равных длинах O(n²). break при нахождении меняет лучший случай, но не худший: если элемента нет, внутренний цикл всё равно дойдёт до конца.

Покажите, что видите вложенность, спрятанную от глаз:

• оператор in на списке: for a in A: if a in B это тот же двойной цикл, внутренний просто скрыт;
• методы списка: list.index, list.remove, list.count линейные, внутри цикла дают квадрат;
• все пары: цикл по j от i + 1 даёт n(n-1)/2 сравнений, это всё ещё O(n²), константа в асимптотике не учитывается.

Дальше способы улучшить:

• хэш-множество: set(B) строится за O(m), проверка in в среднем O(1), итого O(n + m) по времени и O(m) дополнительной памяти;
• сортировка: отсортировать оба списка и пройти двумя указателями, O(n log n + m log m) без хэш-таблицы;
• векторизация: np.isin, df["col"].isin(values), pd.merge работают через хэширование или сортировку в скомпилированном коде, а не в интерпретаторе.

Добавьте, что асимптотика описывает рост, а не скорость на малых данных: на десяти элементах двойной цикл никто не заметит, а на выборке в миллионы строк это часы.

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

Называют O(n), потому что «есть break». По умолчанию сложность оценивают по худшему случаю, и интервьюер ждёт именно его.

Не видят in на списке внутри цикла и сдают «линейное» решение, которое на деле квадратичное.

Говорят, что множество даёт O(1) всегда. Это средний случай: при массовых коллизиях проверка деградирует до линейной, а само множество занимает память.