Какова пространственная сложность этого кода

Question

Что такое космическая сложность кода:

function double(n) {         //Here n is an array
   newArr = [];
   for (i = 0; i < n.length; i++) {
     newArr.push(2 * n[i]);
   }
  return newArr;
}

Answer 1

Сложность пространства действительно равна O(N), потому что пространство зависит не от того, сколько переменных ваша программа определила, а от того, какое количество места она в конечном итоге займет во время выполнения.

---

Думайте о сложности пространства как о факторе стоимости памяти, которую ваша программа будет нести во время выполнения. Если приложение выделяет всю память, которая ему когда-либо понадобится на время выполнения программы, в начале программы, и эта сумма не зависит от каких-либо переменных в программе, тогда коэффициент просто равен 1, то есть сложность пространства равна * 1008. * - константа, потому что она не меняется.

Это может сбивать с толку, потому что вы можете задаться вопросом, почему ваша простая программа имеет сложность пространства O(N), но случайное приложение C, которое выделяет 1GB памяти в начале, просто O(1). Все сводится к фактору - если пространство зависит от переменной в программе, то пространство является фактором этой переменной, иначе пространство равно константа .

Не позволяйте этому сбить вас с толку, но и не позволяйте этому обмануть вас, когда кто-то говорит, что определенная программа имеет сложность O(1), а другая - O(N); O(1) не всегда означает меньше места, и O(N) не обязательно означает больше места. Сложность пространства просто говорит о том, как количество места, необходимое программе, зависит от времени выполнения самой программы.

Answer 2

Поскольку он имеет две переменные newArr и i, от которых зависит пространство этого кода.

Мало того, что есть только две названные переменные, newArr и i, есть также n переменные с именами newArr[0], newArr[1], newArr[2], вплоть до newArr[n-1].Пространственная сложность относится к тому, как увеличивается объем хранения вашего алгоритма относительно количества входных данных.Поскольку вы помещаете не более n элементов в newArr, сложность пространства составляет O(n).