Какова оптимальная сложность по времени и памяти для задачи

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

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

Как отвечать

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

В Python оценку портят операции, которые выглядят дешёвыми:

• x in list: линейный поиск. Внутри цикла это уже O(n²), для проверок нужен set или dict со средним O(1);
• list.pop(0) и insert(0, x): сдвигают весь список, для очереди есть collections.deque;
• срезы: a[1:] копирует данные, и в рекурсии это незаметная квадратичная память;
• склейка строк в цикле: s += x может копировать строку на каждом шаге, надёжный вариант "".join(parts);
• sorted() и list.sort(): O(n log n) по времени и до O(n) дополнительной памяти;
• heapq.nlargest(k, a): O(n log k) вместо полной сортировки, когда нужны первые k.

Память считайте вместе со стеком: рекурсия глубиной n занимает O(n), а sys.getrecursionlimit() по умолчанию возвращает 1000. Генератор вместо списка снимает O(n) памяти, если данные нужны один раз.

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

Называют сложность без оговорки «в среднем». У dict и set O(1) это средний случай, при массовых коллизиях поиск деградирует до O(n), а у быстрой сортировки худший случай O(n²), а не O(n log n).

Забывают про память, которую создали сами: копии срезов, промежуточные списки в списковых включениях, словарь на весь вход. Интервьюер спрашивает про оба ресурса, и ответ только про время засчитывается наполовину.

Путают асимптотику с реальной скоростью. Встроенная функция на C с O(n log n) при небольших n часто обгоняет самописный цикл с O(n) на чистом Python, и об этом стоит сказать, если вас спросят, что вы выбрали бы в продакшене.