数组元素求和算法空间复杂度为O(n)的原因及计算规则咨询

问题解答 #

1. 你对该算法空间复杂度的判断是正确的 #

你给出的求和算法：

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

运行过程中仅使用了sum、i两个临时变量，额外空间占用不随输入数组的长度n变化，因此常规语境下的空间复杂度为O(1)，你的认知没有问题。

2. 「O(n)」的说法来自两种复杂度统计口径的差异 #

行业内对空间复杂度的统计存在两种标准，这是造成认知分歧的核心原因：

• 辅助空间复杂度（绝大多数场景默认标准）：仅统计算法运行过程中，除输入数据本身占用的空间外，额外申请的内存空间。我们平时做算法优劣对比、面试/题解里说的空间复杂度，默认都是这个标准，所以线性搜索、冒泡排序这类不需要额外随输入规模扩展开空间的算法，都会被判定为O(1)空间复杂度。
• 总空间复杂度（极少使用）：统计算法运行全周期占用的所有空间，包含输入数据本身的大小。如果按这个标准计算，你给出的求和算法输入的数组长度为n，总占用空间和n正相关，才会得到O(n)的结论。这种统计方式仅会在评估程序整体内存上限、嵌入式开发等特殊场景下使用，不用于常规算法分析。

3. 关于你提到的计算公式说明 #

你看到的Space complexity = Input size + Auxillary space公式，对应的是上面说的「总空间复杂度」的计算逻辑。常规算法分析不需要考虑输入大小，只需要计算辅助空间即可，这个认知是完全正确的。

内容的提问来源于stack exchange，提问作者Sneha Mathadawar