Время и память

Пространственная сложность измеряет, сколько дополнительной памяти использует алгоритм как функция размера входа n. Как и временная сложность, мы выражаем память нотацией Big-O: O(1), O(n), O(n²), и так далее.

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

Вот главная идея: ты часто можешь менять память на время, или время на память.

Пример 1: найти дублирующийся элемент в массиве

Подход с вложенным циклом (медленный, бережливый):

function hasDuplicate(numbers) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] === numbers[j]) return true;
    }
  }
  return false;
}

Временная сложность: O(n²) (вложенные циклы). Пространственная сложность: O(1) (только пара переменных, i и j).

Алгоритм сравнивает каждую пару элементов. Медленный, почти не использует дополнительную память.

Подход со множеством (быстрый, жадный):

function hasDuplicate(numbers) {
  const seen = new Set();
  for (let num of numbers) {
    if (seen.has(num)) return true;
    seen.add(num);
  }
  return false;
}

Временная сложность: O(n) (один цикл, каждый поиск мгновенен). Пространственная сложность: O(n) (множество хранит до n значений).

Алгоритм создаёт структуру, которая запоминает все значения, которые ты видел. Когда встречаешь новое значение, спроси: «видел ли я тебя раньше?» — множество ответит мгновенно. Время падает до линейного. Память растёт до n.

Это компромисс между временем и памятью: потратить O(n) памяти, чтобы сэкономить O(n²) времени. Это выгодная сделка.

Чтение памяти из кода:

Считай новые данные, которые ты создаёшь:

• Несколько переменных (x, y, count) → O(1) (постоянная память).
• Новый массив размером n → O(n) памяти.
• Новый двумерный массив размером n × n → O(n²) памяти.
• Рекурсия, которая вызывает себя n раз в глубину → O(n) памяти стека.

Рекурсия трудна. Каждый вызов функции резервирует памяти стека для переменных этого вызова. Если твоя рекурсия n в глубину, то у тебя есть n вызовов на стеке, поэтому O(n) памяти.

Пример: отсчёт рекурсивно.

function countdown(n) {
  if (n === 0) return;
  console.log(n);
  countdown(n - 1);
}

Для countdown(1000) стек вызовов растёт в глубину на 1000. Каждый уровень хранит переменные (n, адрес возврата). Итого: O(n) памяти стека. Если переписать это как цикл, стек остаётся мелким — O(1) памяти.

Спектр компромисса между временем и памятью:

Большинство алгоритмов живут где-то в спектре:

• O(1) время, O(1) память — редко (простой поиск или проверка).
• O(n) время, O(1) память — бережливо (просканировать вход, не запоминать).
• O(n) время, O(n) память — сбалансировано (просканировать и запомнить).
• O(n²) время, O(1) память — медленно, но бережливо (перебор без помощи).
• O(n log n) время, O(n) память — эффективно (merge sort, с дополнительным массивом).

Ты не всегда можешь добиться одновременно быстрого времени и низкой памяти. Выбирай мудро, основываясь на своих ограничениях. Если память тесна (встроенная система, мобильный телефон), выбери бережливый подход. Если скорость критична (система реального времени, пользователь ждёт ответа), потрать память, чтобы ускориться.