Какова временная сложность решения в нотации O

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

Умеете ли вы оценить собственный код, а не пересказать таблицу сложностей. Вопрос звучит после того, как вы написали решение, и следом почти всегда идут «а можно быстрее?» и «сколько памяти?».

Как отвечать

Сначала назовите, что такое n: число строк, длина строки, число признаков. Если входов несколько, заведите несколько переменных, n и m, и не сливайте их в одну.

Потом пройдите по своему коду сверху вниз вслух:

• циклы: последовательные складываются, вложенные перемножаются;
• встроенные операции: sorted стоит O(n log n), x in list O(n), x in set и доступ к dict O(1) в среднем. Срез копирует элементы и стоит O(k) от своей длины, а склейка строк через += в цикле может дать квадрат;
• библиотеки: df.merge по ключу работает через хеширование и близок к линейному, sort_values это O(n log n), groupby около O(n). Векторная операция numpy и цикл for по тем же данным одного класса O, но различаются по скорости на один-два порядка;
• память: какие дополнительные структуры вы создали. Словарь на n элементов это O(n) памяти, и на миллионах строк это важнее лишнего логарифма.

Сформулируйте итог одной строкой: «O(n log n) по времени из-за сортировки, O(n) по памяти на словарь». Если решение можно ускорить, сразу скажите как: заменить вложенный поиск на множество, отсортировать один раз вместо сортировки внутри цикла.

Для ML-задач полезно помнить стоимость базовых алгоритмов: наивный kNN тратит O(n·d) на предсказание одного объекта, поэтому на больших выборках берут приближённый поиск соседей.

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

Говорят «O(n)», не пояснив, что такое n. Для задачи с текстом и словарём это может быть длина текста, число слов или размер словаря.

Не замечают дорогую операцию внутри цикла: list.remove, in по списку или sorted превращают вроде бы линейное решение в O(n²).

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