为什么数组中所有元素和的空间复杂性是O(n)？

Question

下面的算法用于数组中所有元素的和。

function sumofnumbers(a[],n)
   {
     sum=0
     for(i=0 to n)
         sum=sum+a[i]
     print(sum)
   }

有人能帮我做这个算法分析吗。为什么上述算法的空间复杂度为O(n)？在我看来，这一定是O(1)。因为我们在这里不考虑任何额外的空间。我们使用给定的空间来计算数组中元素的和。例如，在对元素排序的一些排序技术中，我们采用额外的数组。

据我所说，，

计算空间复杂性的公式：

 Space complexity = Input size + Auxillary space 

每个算法都包含它所需的/自己的输入大小，即程序执行所需的空间。因此，我们必须只考虑程序执行所需的额外空间(辅助空间)，这不是计算空间复杂性的输入大小。

所以我应用了这个概念，是真的吗？

什么时候考虑两个参数(即输入大小和辅助空间)来计算空间复杂度？因为在一些像线性搜索这样的例子中，我看到有些时候它们没有使用输入大小？

谢谢！！

Answer 1

我相信你是对的。空间复杂度不随N-因此O(1)值的增加而变化。参考https://www.baeldung.com/cs/space-complexity

Answer 2

如果输入较大，则总和也可能很大，从而导致非常数空间。

也就是说，112345 ^ 1235634不能适用于64位整数。因此，您需要更大的空间来保存和(可以是str，或者list，或者链接列表)。