分析 Space 复杂性时的困惑

Question

我正在解决有关 space 复杂性的问题，当我们谈论 space 复杂性时，我们不考虑下面 input.but 使用的 space我从网站上看到的代码，它不应该是 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' 局部整数变量 'sum' 和 'i' 的 4 个字节内存（每个 2 个字节） return 值的 2 个字节内存。

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

Answer 1

不同的作者和网站使用 "space complexity" 表示不同的意思，因此您必须检查特定网页的符号。

https://www.studytonight.com/data-structures/space-complexity-of-algorithms 声明 Space 复杂性 = 辅助 Space + 输入 space （我假设这与您使用的网站有关。）

https://theory.cs.princeton.edu/complexity/book.pdf 将 Space 复杂度定义为排除输入 Space（在这种情况下，输入 space 是只读的），这似乎更正常。

Confusion in analyzing Space complexity