上次我们学习了时间复杂度，那么我们今天就来看看空间复杂度，重点讲解空间复杂度的定义类型及完整示例@mikechen
空间复杂度定义
空间复杂度，英文名为Space complexity，是指算法编写成程序后，在计算机中运行时所需存储空间大小的度量。
存储空间一般包括三个方面：
- 输入数据所占用的存储空间；
- 指令常数变量所占用的存储空间；
- 辅助存储空间。
一般空间复杂度表示为S(n) = O(f(n))，其中n表示输入规模，fn表示一段程序代码。
空间复杂度类型
空间复杂度涉及的空间类型有：
1.输入空间
存储输入数据所需的空间大小；
2.暂存空间
算法运行过程中，存储所有中间变量和对象等数据所需的空间大小；
3.输出空间
算法运行返回时，存储输出数据所需的空间大小。
通常情况下，空间复杂度指在输入数据大小为 N 时，算法运行所使用的「暂存空间」+「输出空间」的总体大小。
常见的空间复杂度？
常见的空间复杂度，如下所示：
O(1) < O(log N) < O(N) < O(N^2) < O(2^N)
上面我们了解了什么是空间复杂度，下面一起来看几个空间复杂度的经典例子，就更清楚了，let’s go!
空间复杂度示例
1.常数 O(1)
常量空间的意思是该场景空间复杂度和输入规模n无关，那么常量空间的空间复杂度就可以表示O(1)。
比如：普通常量、变量、对象、元素数量与输入数据大小 N 无关的集合，皆使用常数大小的空间。
示例：
int i = 1; int j = 2; int m = i + j;
代码中的 i、j、m 所分配的空间都不随着处理数据量变化，因此它的空间复杂度 S(n) = O(1)。
2.线性 O(N)
元素数量与 N 呈线性关系的任意类型集合，比如：常见于一维数组、链表、哈希表等，皆使用线性大小的空间。
示例：
int[] m = new int[n]
for(i = 1; i <= n; ++i) {
j = i;
j++;
}
这段代码中，第一行new了一个数组出来，这个数据占用的大小为n，后面虽然有循环，但没有再分配新的空间，因此，这段代码的空间复杂度主要看第一行即可，即 S(n) = O(n)。
3.平方 O(N^2)
元素数量与 N 呈平方关系的任意类型集合，常见于:矩阵，皆使用平方大小的空间。
示例：
for (i = 0; i < n; i++)
{
for (j = 0; j < n; j++)
{
//... }
}
该算法for循环：最外层循环每执行一次，内层循环都要执行n次，执行次数是根据n所决定的，最大时间复杂度是O（n^2），如果内层循环在某种场景一次就跳出,其实也可以退化成o(n)。
4.指数 O(2^N)
指数阶常见于二叉树、多叉树。例如，高度为 N 的「满二叉树」的节点数量为 2^N，占用 O(2^N) 大小的空间。
同理，高度为 N 的「满 m 叉树」的节点数量为 m^N，占用 O(m^N) = O(2^N) 大小的空间。
5.对数 O(logN)
对数阶常出现于分治算法的栈帧空间累计、数据类型转换等。
作者简介
陈睿|mikechen，10年+大厂架构经验，BAT资深面试官，就职于阿里巴巴、淘宝、百度等一线互联网大厂。
👇阅读更多mikechen架构文章👇
阿里架构 |双11秒杀 |分布式架构 |负载均衡 |单点登录 |微服务 |云原生 |高并发 |架构师
以上
关注作者「mikechen」公众号，获取更多技术干货！
后台回复【架构】，即可获取《阿里架构师进阶专题全部合集》，后台回复【面试】即可获取《史上最全阿里Java面试题总结》