re:re:actable
Урок 042 минуты чтения

Как считать пространственную сложность?

На этой странице
Кратко

Пространственная сложность показывает, сколько дополнительной памяти использует алгоритм при росте 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 нужно оговаривать.

Документация

Wikipedia: Space complexity.

Дочитали до конца?
Отметьте урок — прогресс сохранится в браузере.

Поиск

Поиск по урокам