Пространственная сложность

Когда вы инициализируете переменные, такие как массивы или строки, ваш алгоритм выделяет память. Мы никогда не учитываем пространство, используемое входными данными (это плохая практика изменять входные данные), и обычно не учитываем пространство, используемое выходными данными (ответом), если интервьюер не попросит нас об этом.

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

Этот алгоритм имеет пространственную сложность O(1). Единственное выделенное пространство - это целочисленная переменная num, которая является постоянной относительно n.

// Дан целочисленный массив "arr" длиной n

for (let num of arr) {
  console.log(num);
}

Этот алгоритм имеет пространственную сложность O(n). Массив doubledNums хранит n целых чисел в конце алгоритма.

// Дан целочисленный массив "arr" длиной n

let doubledNums = [];

for (let num of arr) {
  doubledNums.push(num * 2);
}

Этот алгоритм имеет пространственную сложность O(n). Массив nums хранит первые 1% чисел в arr. Это дает пространственную сложность O(n / 100) = O(n).

// Дан целочисленный массив "arr" длиной n

let nums = [];
let oneHundredth = Math.floor(n / 100);

for (let i = 0; i < oneHundredth; i++) {
  nums.push(arr[i]);
}

Этот алгоритм имеет пространственную сложность O(n⋅m). Мы создаем сетку размером n⋅m.

// Даны целочисленные массивы "arr" длиной n и "arr2" длиной m,

let grid = Array.from({ length: arr.length }, () => Array(arr2.length).fill(0));

for (let i = 0; i < arr.length; i++) {
  for (let j = 0; j < arr2.length; j++) {
    grid[i][j] = arr[i] * arr2[j];
  }
}

В этом курсе мы будем подробно говорить о временной и пространственной сложности. Если это новая концепция для вас, не беспокойтесь - с практикой вы будете все более и более комфортно анализировать алгоритмы самостоятельно.