算法在编写成可执行程序后，运行时需要耗费时间资源和空间（内存）资源。因此衡量一个算法的好坏，一般是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期，存储容量很小，所以对空间复杂度很是在乎。随着硬件发展，如今我们虽然不需要像过去那样特别关注空间复杂度，但在设计高效算法时，它依然是评估性能的重要指标。
大 O 的渐进表示法回顾
大 O 符号（big O notation）：是用于描述函数渐进行为的数学符号。
推导大 O 阶的方法如下：
- 用常数 1 取代运行时间中的所有加法常数；
- 在修改后的运行次数函数中，只保留最高阶项；
- 如果最高阶项存在且其系数不是 1，则去除与这个项相乘的系数。得到的结果就是大 O 阶。
一、算法的空间复杂度
算法空间复杂度的定义：
- 空间复杂度也是一个数学表达式，是对一个算法在运行过程中额外临时占用存储空间大小的量度。
- 空间复杂度不是程序占用了多少 bytes 的空间，因为这个也没太大意义，所以 空间复杂度算的是变量的个数。
- 空间复杂度计算规则基本跟时间复杂度类似，也使用大 O 渐进表示法。
注意： 函数运行时所需要的栈空间（存储参数、局部变量、一些寄存器信息等）在编译期间已经确定好了，因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。
二、常见空间复杂度计算举例
1. 动态开辟二维数组
int** fun(int n) {
int** s = (int**)malloc(n * sizeof(int*));
for (size_t i = 0; i < n; ++i) {
s[i] = (int*)malloc((i + 1) * sizeof(int));
}
return s;
}
解析： 这里开辟的是一个二维数组，数组有 n 行，每行分别有 1, 2, 3, …, n 列。总元素个数为 ，即 。根据大 O 推导法则，忽略低阶项和系数，空间复杂度为 。