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

Что такое пространственная сложность?

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

Как оценивать?

Для оценки пространственной сложности следуйте этим шагам:

• Определите, какие переменные и структуры данных создаются в алгоритме.
• Оцените, как их размер зависит от размера входных данных (n).
• Игнорируйте константные множители и младшие члены, используя нотацию Big O.
• Учитывайте память для рекурсивных вызовов (глубина рекурсии).

Примеры

Рассмотрим несколько примеров на JavaScript:

// O(1) — константная память
function sum(arr) {
  let total = 0;
  for (let i = 0; i < arr.length; i++) {
    total += arr[i];
  }
  return total;
}

// O(n) — линейная память
function duplicate(arr) {
  let newArr = [];
  for (let i = 0; i < arr.length; i++) {
    newArr.push(arr[i] * 2);
  }
  return newArr;
}

// O(n^2) — квадратичная память
function createMatrix(n) {
  let matrix = [];
  for (let i = 0; i < n; i++) {
    matrix[i] = [];
    for (let j = 0; j < n; j++) {
      matrix[i][j] = i * j;
    }
  }
  return matrix;
}

В первом примере используется только одна переменная total, поэтому память не зависит от n — O(1). Во втором создаётся новый массив размером n — O(n). В третьем создаётся двумерный массив n×n — O(n²).

Рекурсия

При рекурсии важно учитывать глубину стека вызовов. Например, рекурсивный факториал:

function factorial(n) {
  if (n === 0) return 1;
  return n * factorial(n - 1);
}

Здесь глубина рекурсии равна n, поэтому пространственная сложность O(n) из-за стека вызовов.

Вывод

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