共计 4708 个字符，预计需要花费 12 分钟才能阅读完成。
你好，我是长远，这周咱们持续聊算法，接着上次的工夫复杂度，咱们进行对于空间复杂度的解说。
公众号首发：【长远讲算法②】什么是空间复杂度？
博客原文：https://www.aiyc.top/1980.html
常识回顾
首先，咱们来对上周的工作进行大略的温习。
算法是什么？
- 从实践层面来讲，算法就是咱们写程序写代码的优化手册，它教会咱们怎么让代码运行起来更快，或者占用的内存空间更少。直观层面来讲便是，算法是一系列程序指令，用于解决特定的运算和逻辑问题。一个算法是好是坏，咱们通常依据工夫复杂度和空间复杂度去评估。
工夫复杂度是什么？
- 工夫复杂度是对一个算法运行工夫长短的量度，用大 O 示意，常见的工夫复杂度依照从低到高的程序，包含 $O(1)、O(logn)、O(n)、O(nlogn)、O(n^2)$ 等。
工夫复杂度的要点包含以下内容：
- 基本操作执行次数。即每行代码的执行次数，咱们通过这个来计算咱们所写的代码具体的执行次数。
- 渐进工夫复杂度。计算基本操作执行次数诚然是一种求解工夫复杂度的办法，然而咱们平时写的代码是千奇百怪的，因而通过计算基本操作执行次数失去的数字或函数大多都比较复杂，并不适宜间接充当咱们的工夫复杂度，因而咱们引入了渐进工夫复杂度的概念，渐进工夫复杂度罕用大 O 符号表述，不包含这个函数的低阶项和首项系数。应用渐进工夫复杂度可保障咱们算出的工夫复杂度函数相比起根本执行操作次数总和更加简洁。
空间复杂度和工夫复杂度的关系
空间复杂度和工夫复杂度，这两个东西长得十分的像，但到底有什么区别呢？
从文字的角度，咱们能够联想到，工夫个别是咱们摸不着的，比拟形象的货色。而空间个别是现实存在的，咱们能摸到的，比拟具体的货色。
再从平时咱们思考的角度讲，咱们去剖析一件事件，个别要从实践和理论两种层面上进行剖析。比方我想去游览，实践上我只有有钱，有工夫，我就能够进来游览。然而从事实的层面去思考这件事就很繁琐，咱们要想到：以后节令上是否适宜游览，本人是否要先向学校或者下班的中央销假报备，而后再思考订哪天的机票，以及目的地的选取等等琐事。
编程也并不是一件虚构的事件，它是切实存在且在生活中被频繁应用的，因而咱们有必要从实践和理论两种方面思考本人所写的代码的可行性。
工夫复杂度就是咱们对本人代码的“实践剖析”。从咱们集体编程的角度而言，咱们的代码仅用于个人电脑应用，并不参加企业开发，所以咱们个别不去思考计算机的性能。单纯的思考了，怎么写这段代码，它不会出错，能够正确执行。在进行数据结构和算法的学习之后，咱们缓缓的开始思考本人代码的工夫复杂度。即如何让本人写的代码运行速度的更快一些。
空间复杂度便是咱们对本人代码的“理论剖析”。可能咱们集体写代码领会不到空间复杂度的重要性。假如你在大型企业下班，你的老板要求你开发一个手机利用，这个时候，咱们要思考的就不仅仅是，我写的代码能不能失常运行起来这件事了，因为你要站在用户的角度去思考，你的体验度是怎么样的，作为手机利用的使用者，咱们天然会想到，我心愿这个手机利用可能秒开，而不是点进去半天能力加载进去，同时也心愿这个手机利用占手机的内存少一点。而作为老板，让员工开发利用的时候，也心愿公司提供的电脑能平安实现开发，不心愿呈现因为代码运行工夫过长而耗费电脑硬件，导致电脑坏掉迁延我的项目停顿的事件产生。
空间复杂度有着相似于工夫复杂度的概念：一个算法或程序的空间复杂度定性地形容该算法或程序运行所须要的存储空间大小。空间复杂度是相应计算问题的输出值的长度的函数，它示意一个算法齐全执行所须要的存储空间大小。
和工夫复杂度相似，空间复杂度通常也应用大 O 记号来渐进地示意，即空间复杂度也有渐进空间复杂度一说。例如 $O(n)$、$O(nlogn)$、$O(n^α)$、$O(2^n)$ 等；其中 n 用来示意输出的长度，该值能够影响算法的空间复杂度。
就像工夫复杂度的计算不思考算法所应用的空间大小一样，空间复杂度也不思考算法运行须要的工夫长短。
空间复杂度
从整个程序来探讨的话，程序的空间复杂度能够齐全用程序代码自身所占用的存储空间多少来示意。
首先，程序本身所占用的存储空间取决于其蕴含的代码量，咱们只有在编程环境下输出代码进行运行，那么这段代码必定会占用电脑的存储空间。想要压缩这部分存储空间，就要求咱们在实现性能的同时，尽可能编写足够短的代码，但从这一方面来讲，过于宏大，毕竟咱们编写一段代码，其中蕴含着很多内容，咱们将持续将代码拆分剖析为以下两种状况去推算空间复杂度。
个别一段代码的空间复杂度波及到的空间类型有：
1.. 输出、输入空间。程序中如果须要输入输出数据，也会占用肯定的存储空间。程序运行过程中输入输出的数据，往往由要解决的问题而定，即使所用算法不同，程序输入输出所占用的存储空间也是相近的。即，无论是咱们应用 10 行代码还是三行代码去实现同一个问题，他们最终输入的货色一样的话，即便二者代码长度不尽相同，然而输入所占的存储空间是差不多大的。
2.. 暂存空间。程序在运行过程中，可能还须要长期申请更多的存储空间。事实上，对算法的空间复杂度影响最大的，往往是程序运行过程中所申请的长期存储空间。不同的算法所编写出的程序，其运行时申请的长期存储空间通常会有较大不同。
通常状况下，空间复杂度指在输出数据大小为 N 时，算法运行所应用的「暂存空间」+「输入空间」的总体大小。
先来看几种常见的空间复杂度。咱们依据代码来进行详细分析。
常量空间
当算法的存储空间大小固定，和输出规模没有间接的关系时，空间复杂度记作 $O(n)$ .
void fun1(int n){
int var = 3;
...
}def fun1(n):
var = 3
...解说 python 代码：
咱们定义了 fun1() 函数，当咱们调用这个函数的时候，咱们要向其中传入一个参数 n，然而 n 传入后，函数 fun1() 做了一件事，它里层引入了一个 var 变量 并给它赋值 3，但这所有并没有扭转咱们输出的参数 n 的值和类型。依据上文第二条“程序中如果须要输入输出数据，也会占用肯定的存储空间”，咱们输出的参数 n 从头至尾没有产生扭转，因而程序所占的存储空间也没有产生扭转。所以该程序的空间复杂度为 $O(1)$ .
线性空间
当算法调配的空间是一个线性的汇合（如列表或数组），并且汇合大小和输出规模 n 成正比时，空间复杂度记作 $O(n)$ .
void fun2(int n){int[] array = new int[n];
...
}def fun2(n:int):
array_list = [for x in range(1,n)]
...解说 python 代码：
咱们定义了 fun2() 函数，当咱们调用这个函数的时候，咱们向其中传入一个参数 n，参数 n 的类型为 int（整数类型），而后 n 被传入后，函数 fun2() 利用 n 做了一件事：定义了一个长度为 n，元素为从 1 到 n 的列表 array_list。咱们原本的输出规模为 n，由上文中“程序在运行过程中，可能还须要长期申请更多的存储空间”可知，在函数内咱们引入了长度为 n 的列表。即在这个程序中，咱们额定申请了 n 长度的一维列表，与输出规模 n 成正比，所以该程序的空间复杂度记为 $O(n)$.
二维空间
当算法调配的空间是一个二维列表或数组汇合，并且汇合的长度和宽度都与输出规模 n 成正比时，空间复杂度记作 $O(n^2)$.
void fun3(int n){int[][] matrix = new int[n][n];
...
}def fun3(n:int):
matrix_list = []
for i in range(n):
matrix_list.append([0]*n)
...对 python 代码进行解说：
咱们新建了一个函数 fun3() , 它的目标是新建一个 $n×n$ 的二维列表，咱们的做法是：首先新建一个空的列表 matrix_list 而后对 matrix_list 进行一维列表的迭代和增加，最初生成二维列表。首先咱们从生成一维列表开始，将 n 传入 fun3() 中，咱们首先新建一个空列表，为之后向列表中增加元素做筹备，而后咱们要略微动一下脑子，当新建一个长度为 n 元素全为 0 的一维列表时，咱们应用了循环来进行列表的初始化，所以在新建二维列表时，咱们能够用相似的办法，同样应用循环来进行初始化，在一维列表初始化过程中，咱们是不是将 0 元素挨个增加到列表中，以实现有 n 个 0 的列表，那当初咱们要生成领有 $n×n$ 个 0 的列表，那是不是将 [0] 做 n 次循环增加到 matrix_list 中就能够了。而后咱们依据“程序在运行过程中，可能还须要长期申请更多的存储空间。”这一点可知，咱们传入的参数 n 与二维列表 $n×n$ 的长度成正比。所以该代码空间复杂度即为 $O(n^2)$.
以下咱们应用了当 n 为 2 时的状况，进行了函数模仿。
递归空间
程序调用函数是基于栈实现的，函数在调用期间，引入一个栈并进行入栈操作，将调用来的函数以及其参数信息全都压入栈中，当函数进行 return 操作时，执行出栈操作，把上一次调用的函数和参数信息从栈中弹出。从而开释掉多余的内存。
int fun4(int N){if(N <= 1){return 1;}
return fun4(N - 1) + 1;
}def fun4(N:int):
if N <= 1: return 1
return fun4(N - 1) + 1对 python 代码进行剖析：
当咱们输出的 $N<=1$ 时，咱们将间接返回 1，这是咱们的递归完结点。当咱们输出的 N 大于 1 时，程序会引入一个栈，将 fun4(N) 放入栈中，而 fun4(N) 又要调用 fun(N - 1) + 1 因而咱们将 fun(N - 1) - 1 放入栈中，以此类推直到 N 变为 1，这是 咱们找到了递归完结点，将栈内的函数全都挨个释放出来即可。由下面函数的出入栈过程能够看出，执行递归操作所须要的内存空间和递归的深度成正比。纯正的递归操作的空间复杂度也是线性，但如果递归的深度是 n，那么空间复杂度就是 $O(n)$.
咱们在这里给出当 N = 6 时的程序模仿以及递归树不便读者进行了解（递归后续会进行具体解说）。
工夫和空间的衡量
在上文笔者也提到，写代码其实不是一件虚构的事件，它波及到了事实的很多状况，当你在企业工作时，你所写的代码并不是单单满足你本人的需要即可，而是要思考各种各样事实的限度了。尽管随着科技的倒退，电脑更新换代十分的快，性能也是越来越弱小。但电脑的内存并不是有限的，它的性能究竟是无限的。因而咱们在写代码的时候也要“精打细算”，抉择更加高效的执行方法。
对于算法的性能，须要从工夫和空间的应用状况来综合评估。好的算法应具备两个个性，即工夫和空间复杂度均比拟低。而实际上，对于某个算法问题，正因为电脑的能力是无限的，所以咱们的工夫复杂度和空间空间复杂度是没有方法同时兼顾的，因而将会呈现，工夫换空间或者空间换工夫的状况产生。
因为当初科技倒退很快，电脑性能个别比拟弱小，满足了咱们的日常需要，所以在平时的代码编写过程中，咱们绝大多数状况，会思考空间换取工夫的操作，多调配一些内存空间，让程序跑到更快。
总结
- 什么是空间复杂度？
空间复杂度是对一个算法在运行过程中长期占用存储空间大小的量度，用大 O 示意，常见的空间复杂度依照从低到高的程序，包含 $O(1)、O(n)、O(n^2)$ . 其中递归算法的空间复杂度和递归深度成正比。
关注微信公众号：AI 悦创。不迷路。下次咱们进行数据结构的解说。
AI 悦创·推出辅导班啦，包含「Python 语言辅导班、C++ 辅导班、算法 / 数据结构辅导班、少儿编程、pygame 游戏开发」，全部都是一对一教学：一对一辅导 + 一对一答疑 + 安排作业 + 我的项目实际等。QQ、微信在线，随时响应！V：Jiabcdefh
