算法空间复杂度

水深无声 2023-10-05 18:18 15阅读 0赞

在 [算法时间复杂度][Link 1] 中，我们一块了解了算法时间复杂度相关的内容，比如常见的时间复杂度、时间复杂度的计算、以及提供了几个简单的例子来推算时间复杂度。今天就一块来了解下算法的空间复杂度。

首先说下空间，拿吃饭举例子吧：咱们把做好的菜从锅里吃到肚里是需要碗的吧（你要是就着锅吃饭那就……），如果锅里的菜很多你还想一次性弄出来，是不是有两种方案。一种是找个尽可能大的碗，一种是找很多个碗。算法也是一样，数据从输入到输出中间的处理过程是需要容器的，换句话说就是需要空间的。

在上篇介绍时间复杂度的时候，我们知道了说一个算法的时间复杂度并不是说一个算法的具体的执行时间的。空间复杂度也同理，并不是说一个算法执行需要的具体空间大小。

### 定义 ###

说下具体的定义吧：算法的空间复杂度通过计算算法所需的存储空间实现，算法空间复杂度的计算公式记作：S(n)=O(f(n))，其中，n为问题的规模，f(n)为语句关于n所占存储空间的函数。

上段话中有个重点需要说下，和我举的例子也是有关系的：所需的存储空间指的是一个算法在运行过程中的**临时占用存储空间**，就像我举例中的碗一样，只是临时用的。

> 一个算法在计算机存储器上所占用的存储空间，包括存储算法本身所占用的存储空间，算法的输入输出数据所占用的存储空间和算法在运行过程中临时占用的存储空间这三个方面。

### 几种情况 ###

#### 常量空间 ####

类似于时间复杂度 O(1)，当算法的存储空间大小固定，和输入规模没有直接的关系时，空间复杂度记作O(1)。

int m = 2;

#### 线性空间 ####

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

int[] array = new int[n]

#### 二维空间 ####

当算法分配的空间是一个二维数组集合，并且集合的长度和宽度都与输入规模 n 成正比时，空间复杂度记作 O( n 2 n^2 n2)。

int[][] matrix = new int[n][n];

> 类似时间复杂度，如果为 `int[][] matrix = new int[m][n];` 的话，复杂度就是 O( m n mn mn) 了。

#### 递归空间 ####

先说下递归吧，说白了就是自己调用自己，比如下面的代码：

void fun4(int n){
        
    	if(n<=1){
        
    		return;
    	}
    	fun4(n-1);
    	…
    }

再说下递归空间吧，正如上述代码一样，递归代码中没有显示声明变量或者集合，但是计算机在执行程序时，会专门分配一块内存，用来存储“方法调用栈”。方法调用栈包括入栈和出栈两个操作：

*  当进入一个新方法时，执行入栈操作，把调用的方法和参数信息压入栈中。
 *  当方法返回时，执行出栈操作，把调用的方法和参数信息从栈中弹出。

还是上述代码，假设现在传入参数 5，那么方法 fun4(5) 的调用信息先入栈：  
![在这里插入图片描述][20210123213054591.png]  
接下来递归调用相同的方法，方法 fun4(4) 的调用信息入栈：  
![在这里插入图片描述][20210123213144794.png]  
依次类推，递归越来越深，栈内的元素也越来越多，最终形成下图：  
![在这里插入图片描述][20210123213226498.png]  
当 n=1 的时候，触发递归的结束条件，执行 return，方法出栈。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]  
最终，所有入栈的元素都会出栈。

由上面“方法调用栈”的出入栈过程可以看出，执行递归操作所需要的内存空间和递归的深度成正比。纯粹的递归操作的空间复杂度也是线性的，如果递归的深度是n，那么空间复杂度就是 O(n)。

> 此部分的栈的相关特性以后会有博文介绍，请期待~

### 两种思想 ###

时间换空间与空间换时间

> TODO：等看力扣的时候补充具体的案例

[Link 1]: https://mindartisan.blog.csdn.net/article/details/112691301
[20210123213054591.png]: https://img-blog.csdnimg.cn/20210123213054591.png
[20210123213144794.png]: https://img-blog.csdnimg.cn/20210123213144794.png
[20210123213226498.png]: https://img-blog.csdnimg.cn/20210123213226498.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/2021012321345986.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L01yQmF5bWF4,size_16,color_FFFFFF,t_70