【久远讲算法②】 什么是空间复杂度

【久远讲算法】 什么是空间复杂度

你好，我是久远，这周我们继续聊算法，接着上次的时间复杂度，我们进行关于空间复杂度的讲解。

公众号首发：【久远讲算法②】什么是空间复杂度？

博客原文：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)$ .

代码语言：txt复制

void fun1(int n){
    int var = 3;
    ...
}

代码语言：txt复制

def fun1(n):
    var = 3
    ...

讲解 python 代码：

我们定义了 fun1() 函数，当我们调用这个函数的时候，我们要向其中传入一个参数 n ，但是n传入后，函数 fun1() 做了一件事，它里层引入了一个 var 变量 并给它赋值 3 ，但这一切并没有改变我们输入的参数 n 的值和类型。根据上文第二条 “ 程序中如果需要输入输出数据，也会占用一定的存储空间 ”，我们输入的参数 n 从头至尾没有发生改变，因此程序所占的存储空间也没有发生改变。所以该程序的空间复杂度为 $O(1)$ .

线性空间

当算法分配的空间是一个线性的集合（如列表或数组），并且集合大小和输入规模 n 成正比时，空间复杂度记作$O(n)$ .

代码语言：txt复制

void fun2(int n){
    int[] array = new int[n];
    ...
}

代码语言：txt复制

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)$.

代码语言：txt复制

void fun3(int n){
    int[][] matrix = new int[n][n];
    ...
}

代码语言：txt复制

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 操作时，执行出栈操作，把上一次调用的函数和参数信息从栈中弹出。从而释放掉多余的内存。

代码语言：txt复制

int fun4(int N){
    if(N <= 1){
        return 1;
    }
    return fun4(N - 1)   1;
}

代码语言：txt复制

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悦创。不迷路。下次我们进行数据结构的讲解。

腾讯广告算法大赛

0 人点赞