Как считать пространственную сложность?
На этой странице
Пространственная сложность показывает, сколько дополнительной памяти использует алгоритм при росте input. Обычно считают auxiliary space: новые массивы, Map, Set, recursion stack и другие структуры, созданные во время работы.
Вопрос
Как посчитать пространственную сложность и что входит в дополнительную память?
O(1) память
function max(nums: number[]): number | null {
if (nums.length === 0) return null
let answer = nums[0]
for (const num of nums) {
if (num > answer) answer = num
}
return answer
}Дополнительно храним только одну переменную:
O(1)O(n) память
function unique(nums: number[]): number[] {
return [...new Set(nums)]
}Создаем Set, который в худшем случае хранит n элементов:
O(n)Recursion stack
function factorial(n: number): number {
if (n <= 1) return 1
return n * factorial(n - 1)
}Вызовы лежат в call stack:
O(n)Даже если мы не создавали массив вручную.
In-place не всегда O(1)
In-place означает, что алгоритм меняет input-структуру, но это не всегда гарантирует O(1) memory.
Например, quicksort часто сортирует in-place, но recursion stack может занимать:
average O(log n), worst O(n)Нужно ли считать output?
На собеседованиях обычно уточняют:
- auxiliary space - память помимо результата;
- total space - включая результат.
Например:
function double(nums: number[]): number[] {
return nums.map((x) => x * 2)
}Output занимает O(n). Если считают total space - O(n). Если считают только auxiliary для обязательного output, иногда говорят O(1) additional.
Что отвечать на собеседовании?
Space complexity - это рост дополнительной памяти алгоритма. Я учитываю созданные массивы, объекты, Map, Set, очередь/стек, а также recursion stack. Если функция возвращает новый массив, важно уточнить, считаем ли output memory или только auxiliary space.
Что важно помнить: частые ошибки
- Забывать recursion stack.
- Считать только переменные, но не
MapиSet. - Не уточнять, входит ли output в space complexity.
- Называть in-place алгоритм
O(1)без учета рекурсии. - Игнорировать копии через
slice, spread иtoSorted.
Мини-шпаргалка
- Переменные - часто
O(1). - Новый массив размера
n-O(n). Map/Setдоnэлементов -O(n).- Рекурсия добавляет call stack.
- In-place не всегда значит
O(1). - Output memory нужно оговаривать.