Как оценить сложность по памяти с учетом дополнительной памяти, но без учета входных и выходных данных

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

Знаете ли вы разницу между полной пространственной сложностью и вспомогательной памятью (auxiliary space) и умеете ли честно посчитать вторую, включая стек вызовов. Следом часто дают конкретный код, например сортировку или обход дерева, и просят назвать оценку.

Как отвечать

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

Порядок оценки:

• перечислите структуры: каждый буфер, HashMap, ArrayDeque, промежуточный список от map или filter, и их размер как функцию от n;
• посчитайте стек: глубина рекурсии, умноженная на размер кадра. Сбалансированное дерево даёт O(log n), вырожденное в список уже O(n);
• берите пик, а не сумму: если буферы живут в разное время, в оценку идёт максимальный одновременный объём;

Примеры, которые стоит знать:

• сортировка слиянием массива: O(n) на буфер слияния плюс O(log n) стека;
• быстрая сортировка: в среднем O(log n) на стек, в худшем случае O(n), если не рекурсировать сначала в меньшую часть;
• пирамидальная сортировка: O(1);
• генерация всех подмножеств: выход экспоненциальный, а вспомогательная память O(n) на текущий набор и стек.

Для Android добавьте практическую сторону: асимптотика говорит, как растёт память, а реальный пик и лишние аллокации видны в профайлере памяти Android Studio. Большие промежуточные коллекции в отрисовке или при прокрутке списка дают частые сборки мусора и подёргивания интерфейса.

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

Забывают про стек. Рекурсивный DFS без единого нового массива выглядит как O(1), хотя на деле это O(h), где h высота дерева.

Включают в оценку результат. Функция, которая возвращает отсортированную копию, по вспомогательной памяти может быть O(1), если сортирует прямо в выходном массиве.

Смешивают сложность с утечками памяти. Утечка это ошибка жизненного цикла, например ссылка на Activity из синглтона, а не свойство алгоритма, и ищут её через LeakCanary, а не через Big O.