什么是空间复杂度

• 空间复杂度是指执行算法时所使用的临时变量所占用内存空间的大小，同时间复杂度一样用大写的字母O(数量)来表示。

为什么使用空间复杂度

• 用于判断算法的优劣（算法在时间复杂度相同的情况下，空间复杂度越小的越好）

常见的空间复杂度种类

• 常数空间：算法所占用的空间是固定的，与输入输出无关，记为S(n) = O(1)。
• 线性空间：算法所占用的空间与输入输出成正比，记为S(n) = O(n)。
• 二维空间：算法所分配的是一个集合长度和宽度都与输入规模成正比的二维数组，记为S(n) = O(n²)。
• 递归空间：算法使用递归时，内存会分配一个方法调用栈，和递归深度成正比，与线性空间的空间复杂度相同，记为S(n) = O(n)。