分析空间复杂性的困惑

Question

我正在解决关于空间复杂度的问题，当我们谈论空间复杂度时，我们不考虑输入所使用的空间，但在下面的代码中，我从一个网站上看到，它不是应该是O(1)，为什么他们说它依赖于n？请澄清我很困惑

 int sum(int A[ ], int n)
{
   int sum = 0, i;
   for(i = 0; i < n; i++)
      sum = sum + A[i];
   return sum;
}

在上面的代码中，它需要'n*2'字节的内存来存储数组变量'a[]'2字节的内存来存储整数参数'n'4字节的内存来存储局部整数变量'sum'和'i'（各2字节）2字节的内存来存储返回值。

也就是说，完成它的执行总共需要'2n+8'字节的内存。这里，所需的内存总量取决于'n'的值。随着'n'值的增加，所需的空间也会按比例增加。这种类型的空间复杂度被称为线性空间复杂度。

Answer 1

不同的作者和网站使用 "空间复杂度 "的意思是不同的，所以你必须检查具体网页的符号。

https:/www.studytonight.comdata-structuresspace-complexity-of-algorithms指出空间复杂度=辅助空间+输入空间(我想这与你使用的网站有关。)

https:/theory.cs.princeton.educomplexitybook.pdf。将空间复杂度定义为不包括输入空间（这种情况下输入空间是只读的），这似乎比较正常。