空间复杂度是衡量算法在执行过程中所需内存空间相对于输入规模的指标。虽然时间复杂度（在时间复杂度中讨论）侧重于执行速度，但空间复杂度分析内存使用模式。理解空间复杂度有助于开发者创建内存高效的算法，这在资源受限环境或处理大型数据集时至关重要。
在分析空间复杂度时，我们考虑算法在执行期间使用的内存的几个组成部分。
算法的内存空间包括：
在计算空间复杂度时，我们通常关注临时存储空间和输出空间，而将输入空间排除在我们的分析之外。
来源：[docs/chapter_computational_complexity/space_complexity.md:6-23]
空间复杂度分析检查内存使用如何随输入规模进行扩展。与时间复杂度类似，我们使用大 O 符号 (O) 来表示算法空间需求的上限。
考虑这个展示不同空间复杂度特性的函数
function algorithm(n):
A = 0 # Constant space (independent of n)
b = 0 # Constant space
node = Node(0) # Constant space (object)
arr = new array[n] # Linear space (scales with n)
return sum(arr) # Output space
在此示例中，空间复杂度为 O(n)，因为数组大小随输入 n 呈线性增长。
来源：[docs/chapter_computational_complexity/space_complexity.md:21-120]
不同的算法表现出不同的空间复杂度模式。以下是最常见的类别：
| 复杂性 | 姓名 | 描述 | 示例 |
|---|---|---|---|
| O(1) | 常数空间 | 内存使用不随输入规模改变 | 查找数组中的最大元素 |
| O(log n) | 对数空间 | 内存使用呈对数增长 | 某些二分查找的实现 |
| O(n) | 线性空间 | 内存使用与输入规模成正比增长 | 创建一个与输入长度相同的数组 |
| O(n²) | 平方空间 | 内存使用随输入规模的平方增长 | 创建一个 n×n 的二维矩阵 |
| O(2ⁿ) | 指数空间 | 内存使用随 n 的每个增量而翻倍 | 未使用记忆化的递归斐波那契数列计算 |
具有常数空间复杂度的算法，无论输入规模如何，使用的内存量都是相同的。这些算法内存效率很高。
具有 O(1) 空间复杂度的算法示例——查找数组中的最大值
function findMax(array):
max = array[0] # Single variable regardless of array size
for each element in array:
if element > max:
max = element
return max
来源：[docs/chapter_computational_complexity/space_complexity.md:192-217]
具有线性空间复杂度的算法使用的内存与输入规模成正比。内存需求随输入规模线性增加。
具有 O(n) 空间复杂度的算法示例——创建数组的副本
function arrayCopy(array):
newArray = new Array(array.length)
for i from 0 to array.length-1:
newArray[i] = array[i]
return newArray
来源：[docs/chapter_computational_complexity/space_complexity.md:219-258]
递归算法可能会消耗大量的栈空间。每次递归调用都会向调用栈中添加一个帧，该帧存储局部变量、参数和返回地址。
例如，递归阶乘函数消耗的栈空间与输入成正比
function factorial(n):
if n <= 1:
return 1
else:
return n * factorial(n-1)
该函数具有 O(n) 的空间复杂度，因为它为输入 n 创建了 n 个栈帧。
来源：[docs/chapter_computational_complexity/space_complexity.md:260-360]
算法通常涉及时间复杂度和空间复杂度之间的权衡。有时我们可以通过使用更多内存来降低时间复杂度，或者通过增加运行时间来节省内存。
# With memoization (increased space, reduced time)
function fibWithMemo(n, memo={}):
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fibWithMemo(n-1, memo) + fibWithMemo(n-2, memo)
return memo[n]
# Without memoization (reduced space, increased time)
function fibonacci(n):
if n <= 1:
return n
return fibonacci(n-1) + fibonacci(n-2)
第一个实现使用哈希表进行记忆化，将时间复杂度从 O(2ⁿ) 提高到 O(n)，但需要 O(n) 的空间。第二个实现使用的空间较少（仅递归栈帧），但具有指数时间复杂度。
来源：[docs/chapter_computational_complexity/space_complexity.md:362-402]
在讨论空间复杂度时，我们通常区分：
大多数空间复杂度分析侧重于辅助空间，它反映了除输入之外所需的额外内存。
对于就地算法（直接修改输入），辅助空间复杂度通常是 O(1)，即使总空间复杂度包括了输入大小。
来源：[docs/chapter_computational_complexity/space_complexity.md:404-475]
在开发算法时，请考虑空间复杂度的这些实际方面：
应将空间复杂度与时间复杂度、算法清晰度以及应用程序的特定要求一起考虑。
来源：[docs/chapter_computational_complexity/space_complexity.md:477-530]