编辑“︁空间复杂度”︁

{{Note|本文是[[数据结构与算法学习路径结构]]中[[算法基础]]章节的一部分，主要讲解算法的空间复杂度概念。}}

= 空间复杂度 =

空间复杂度（Space Complexity）是衡量算法在运行过程中临时占用存储空间大小的量度。与[[时间复杂度]]类似，空间复杂度也是算法分析的重要指标之一，用于评估算法对内存资源的消耗情况。

== 基本概念 ==

空间复杂度表示算法在执行过程中所需的存储空间与输入规模之间的关系，通常用大O符号（O）表示。它关注的是算法运行期间额外占用的内存空间，不包括输入数据本身占用的空间。

=== 常见空间复杂度分类 ===

* '''O(1)''' - 常数空间：算法使用的额外空间不随输入规模变化
* '''O(n)''' - 线性空间：算法使用的额外空间与输入规模成正比
* '''O(n²)''' - 平方空间：算法使用的额外空间与输入规模的平方成正比
* '''O(log n)''' - 对数空间：算法使用的额外空间与输入规模的对数成正比

== 计算方法 ==

计算空间复杂度时需要考虑：
1. 程序指令空间（固定）
2. 数据存储空间（变量、常量等）
3. 环境栈空间（函数调用等）

=== 示例分析 ===

<syntaxhighlight lang="python">
# 示例1：O(1)空间复杂度
def constant_space(n):
    total = 0
    for i in range(n):
        total += i
    return total
</syntaxhighlight>

'''解释'''：无论输入n多大，只使用了固定数量的变量（total和i），空间复杂度为O(1)。

<syntaxhighlight lang="python">
# 示例2：O(n)空间复杂度
def linear_space(n):
    lst = []
    for i in range(n):
        lst.append(i)
    return lst
</syntaxhighlight>

'''解释'''：创建了一个与输入n大小相同的列表，空间复杂度为O(n)。

== 递归算法的空间复杂度 ==

递归调用会占用栈空间，需要特别注意：

<syntaxhighlight lang="python">
# 示例3：O(n)空间复杂度的递归
def factorial(n):
    if n <= 1:
        return 1
    return n * factorial(n-1)
</syntaxhighlight>

'''解释'''：每次递归调用都会在调用栈中创建一个新的栈帧，最深会有n层调用，空间复杂度为O(n)。

<mermaid>
graph TD
    A[factorial(3)] --> B[factorial(2)]
    B --> C[factorial(1)]
    C --> D[返回1]
    D --> E[返回2*1=2]
    E --> F[返回3*2=6]
</mermaid>

== 实际应用案例 ==

=== 案例1：图像处理 ===

处理1024x1024像素的图像时：
- 如果算法需要创建同等大小的临时缓冲区，空间复杂度为O(n²)
- 优化算法可能只需O(1)的额外空间

=== 案例2：数据库查询 ===

执行JOIN操作时：
- 朴素算法可能需O(m*n)空间存储中间结果
- 优化算法可能只需O(m+n)空间

== 空间与时间的权衡 ==

算法设计中常需要在时间和空间之间做出权衡：

{| class="wikitable"
|-
! 算法 !! 时间复杂度 !! 空间复杂度
|-
| 朴素斐波那契 | O(2ⁿ) | O(n)
|-
| 动态规划斐波那契 | O(n) | O(n)
|-
| 优化动态规划斐波那契 | O(n) | O(1)
|}

== 数学表示 ==

空间复杂度S(n)的正式定义为：

<math>
S(n) = O(g(n)) \iff \exists c > 0, n_0 > 0 : \forall n \geq n_0, S(n) \leq c \cdot g(n)
</math>

== 优化技巧 ==

* 重用内存空间
* 使用原地算法（in-place）
* 选择适当的数据结构
* 尾递归优化（某些语言支持）

== 常见误区 ==

1. 混淆程序大小与空间复杂度
2. 忽略递归调用的空间消耗
3. 不考虑数据结构本身的开销
4. 忽视多线程环境下的空间需求

== 总结 ==

理解空间复杂度有助于：
* 评估算法内存需求
* 优化资源使用
* 设计更高效的算法
* 避免内存溢出错误

{{Warning|在实际编程中，特别是处理大规模数据时，空间复杂度往往比时间复杂度更容易成为性能瓶颈。}}

== 练习 ==

1. 分析以下函数的空间复杂度：
<syntaxhighlight lang="python">
def matrix_sum(matrix):
    total = 0
    for row in matrix:
        for num in row:
            total += num
    return total
</syntaxhighlight>

2. 比较递归和迭代实现二分查找的空间复杂度差异。

3. 设计一个O(1)空间复杂度的算法来反转数组。

[[Category:计算机科学]]
[[Category:数据结构与算法]]
[[Category:算法基础]]