请解释关于Space complexity的表述：它由Auxiliary space和Input space组成

你提到的表述完全正确：空间复杂度由**辅助空间（Auxiliary space）和输入空间（Input space）**这两部分组成，具体拆解如下：

• 输入空间（Input space）：用于存储算法接收的输入数据的内存空间。比如处理一个长度为n的数组时，这个数组本身占用的内存就属于输入空间，它的大小仅由输入数据的规模决定，和算法的执行逻辑无关。
• 辅助空间（Auxiliary space）：算法在执行过程中，除输入数据外额外申请的内存空间。比如递归调用产生的栈空间、临时变量、用于中间计算的哈希表或数组等，这部分空间是算法为完成计算逻辑而开辟的，直接由算法的实现方式决定。

需要注意的是，日常讨论中常说的“额外空间复杂度”其实特指辅助空间，而完整的空间复杂度是输入空间与辅助空间的总和。

内容的提问来源于stack exchange，提问作者uzHerzeg Herzeg