【数据结构从青铜到王者】第六篇:时间复杂度和空间复杂度

素颜马尾好姑娘i 2023-01-18 02:23 5阅读 0赞

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]

# 系列文章目录 #

--------------------

### 文章目录 ###

*  系列文章目录
 *  前言
 *  一、时间复杂度
 *   *   *  1.时间复杂度的概念
         *  2.大O的渐进表示法
         *  3.时间复杂度经典题目
 *  二、空间复杂度
 *   *   *  1.空间复杂度的概念
         *  2.空间复杂度经典题目
 *  总结

--------------------

# 前言 #

算法效率分析分为两种：第一种是时间效率，第二种是空间效率。时间效率被称为时间复杂度，而空间效率被称作空间复杂度。 时间复杂度主要衡量的是一个算法的运行速度，而空间复杂度主要衡量一个算法所需要的额外空间，在计算机发展的早期，计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

--------------------

![在这里插入图片描述][20210430103013859.png]

# 一、时间复杂度 #

### 1.时间复杂度的概念 ###

时间复杂度的定义：在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。一个算法执行所耗费的时间，从理论上说，是不能算出来的，只有你把你的程序放在机器上跑起来，才能知道。但是我们需要每个算法都上机测试吗？是可以都上机测试，但是这很麻烦，所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法的时间复杂度。

### 2.大O的渐进表示法 ###

计算下面代码的时间复杂度:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 1]

> Func1 执行的基本操作次数 ：  
> N = 10 F(N) = 130  
> N = 100 F(N) = 10210  
> N = 1000 F(N) = 1002010  
> 实际中我们计算时间复杂度时，我们其实并不一定要计算精确的执行次数，而只需要大概执行次数，那么这里我们使用大O的渐进表示法。  
> 大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

> 推导大O阶方法：  
> 1、用常数1取代运行时间中的所有加法常数。  
> 2、在修改后的运行次数函数中，只保留最高阶项。  
> 3、如果最高阶项存在且不是1，则去除与这个项目相乘的常数。得到的结果就是大O阶。  
> 使用大O的渐进表示法以后，Func1的时间复杂度为：  
> N = 10 F(N) = 100  
> N = 100 F(N) = 10000  
> N = 1000 F(N) = 1000000  
> 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项，简洁明了的表示出了执行次数。  
> 另外有些算法的时间复杂度存在最好、平均和最坏情况：  
> 最坏情况：任意输入规模的最大运行次数(上界)  
> 平均情况：任意输入规模的期望运行次数  
> 最好情况：任意输入规模的最小运行次数(下界)  
> 例如：在一个长度为N数组中搜索一个数据x  
> 最好情况：1次找到  
> 最坏情况：N次找到  
> 平均情况：N/2次找到  
> 在实际中一般情况关注的是算法的最坏运行情况，所以数组中搜索数据时间复杂度为O(N)

### 3.时间复杂度经典题目 ###

题目1:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 2]  
此时算法的执行次数是2N+M次，通过推导大O的渐进表示法时间复杂度是O（N+M）。

题目2：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 3]  
此时算法的执行次数是M+N次，有两个未知数，时间复杂度是O（M+N）。

题目3:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 4]  
此时算法的执行次数是100次，由于是常数项，所以时间复杂度是O（1）。

题目四：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 5]  
strchr是在一个字符串中查找一个字符，查找次数最好O（1），最坏O（N），根据大O的渐进表示法所以为O（N）。

题目5:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 6]  
因为比较的数字是n-1,n-2,n-3…3,2,1反过来就是1,2，3，…，n-3，n-2,n-1规律就是一个等差数列根据等差数列求和公式(n^2+n)/2，那么根据大O的渐进表示法就是O（N方）。

题目6:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 7]  
![在这里插入图片描述][20210430114745480.png]  
在一个有序的数组中一直二分直到找到要找的那个数字,那么n/2/2/2…=1,那么就可以变换为2^x=n,那么x就是log以2为底，n的次方，时间复杂度就是O(logN)。

题目7:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 8]  
这个题目求N阶层,那么算法的执行次数就是N，时间复杂度就是O（N）。

题目8:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 9]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]  
由上图知道算法的执行次数为1,2,4,8…是一个等比数列，所以根据大O的渐进表示法时间复杂度是O（2^N）。

# 二、空间复杂度 #

### 1.空间复杂度的概念 ###

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度不是程序占用了多少bytes的空间，因为这个也没太大意义，所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似，也使用大O渐进表示法。

### 2.空间复杂度经典题目 ###

题目1：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 10]  
这里使用的常数个空间，所以空间复杂度是O（1）。

题目2:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 11]  
这里动态开辟了n+1个空间，所以空间复杂度是O(N)。

题目三:  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 12]  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]

这里递归每次调用一次函数，就会开辟一次栈帧，每个栈帧使用了常数个空间，所以空间复杂度为O(N)

# 总结 #

以上就是今天要讲的内容，本文仅仅简单介绍了时间复杂度和空间复杂度使用，对于算法运行时间的快慢和所需要耗费的时间以这两种复杂度来衡量，对我们以后的做题优解有十分大的帮助，我们务必掌握。另外还有，如果上述有任何问题，请懂哥指教，不过没关系，主要是自己能坚持，更希望有一起学习的同学可以帮我指正，但是如果可以请温柔一点跟我讲，爱与和平是永远的主题，爱各位了。  
![在这里插入图片描述][2021043012180682.png_pic_center]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221021/d907d4d896da485792fb878bc829094b.png
[20210430103013859.png]: /images/20221021/470fcc4d94694f7f8714c4bf55985983.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221021/dd6a5d28534d41ff9056485a216c5678.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221021/066675c5acb240b6925cd08ebe832537.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221021/c9dd7bee328b4112bc1bbd8c6c5eb51e.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221021/8165aa15e24f4711b1bcf5b102f3942b.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221021/d6083c375f2d457884f4b02bbef9534d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 6]: /images/20221021/56471bbd47ef41329c24dec1a59e7f43.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 7]: /images/20221021/e3254aefcd00444f9638bb822937c2e3.png
[20210430114745480.png]: /images/20221021/876698eae714450ab7bbaa3295c01cb7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 8]: /images/20221021/20b5ebeec2f8422aa0c9dd7d3659e1f0.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 9]: /images/20221021/62fc3e98c6fe429b9cce49a91e38899d.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70]: /images/20221021/07b0b4359ca740259c725a123a785060.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 10]: /images/20221021/37e1a07e90044960b9c23acc659b6715.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 11]: /images/20221021/e29915a849b0404baa9c3837f0ab82ac.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70_pic_center 12]: /images/20221021/f4c7a4780f08438994e33f33f117f2b9.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTE4MDkw_size_16_color_FFFFFF_t_70 1]: /images/20221021/e079add5e7454fe4bbe897bc78205919.png
[2021043012180682.png_pic_center]: /images/20221021/e1c76d2961f74a7c85fd53dd7e2d3e80.png