C语言的时间复杂度与空间复杂度

ゞ浴缸里的玫瑰 2022-12-12 15:13 141阅读 0赞

昨天简单提到时间复杂度和空间复杂度，今天我们要详细的谈一谈时间复杂度和空间复杂度的计算方法。（所有的图都来自B站小甲鱼老师的课程）。

首先要强调的是，研究算法的复杂度，侧重研究算法随着输入规模扩大增长量的一个抽象，而不是精确地知道需要执行多少次，只是为了比较我们使用哪一个算法更优。

先来谈谈算法的好坏吧！  
例如：第一种算法循环执行了2n+2次；第二种算法循环执行了2次，那么这两种算法我们就可以把它当作其实就是n和1的差距，只需要知道哪种算法更好就行，不需要死算究竟差了多少次！！  
再例如下面这段程序是两层循环，外层循环每执行1次，内层循环都需要执行100次，所以这段程序总共需要执行100\*100次。\[时间复杂度就是O(100^2)\](继续往下看你就明白了）  
如果n更大，如果精确的算它需要执行多少次，那是非常累的！  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]  
我们在分析一个算法的运行时间时，重要的是把基本操作的数量和输入模式关联起来。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]  
从上图中可以看出，随着n的继续增加，算法A1比算法B1逐渐优秀。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]  
从上面这个图中我们可以看出，算法A1和A2（B1和B2）曲线基本重合，所以说明**常数**我们可以基本忽略不计。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]  
从上图发现，算法的好与坏与n前面相乘的系数关系不大，也就是说，算法中**最高次项前面的常数**并不重要。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]  
从上图中可以看出，随着n的增长，算法的好坏与最高次项的**指数**关系更大。

**总结**：判断一个算法的效率时，函数的常数和其他次要项常常可以忽略，更应该关注**最高项的阶数（最高次幂）**。

**时间复杂度**  
算法的时间复杂度，也就是算法的时间量度，记作：  
**T（n）=O(f(n))**。表示：随问题规模n的增大，算法执行时间的增长率和f（n）的增长率相同，称作算法的时间复杂度。其中f(n)是问题规模n的函数。  
一般情况下，随着输入规模n的增大，T（n）的增长最慢的算法为最优算法。  
如何分析一个算法的时间复杂度？  
**——用常数1取代运行时间中的所有加法常数。  
——在修改后的运行次数函数中，只保留最高阶项。  
——如果最高阶项存在且不是1，则去除与这个项相乘的常数。**  
简单的说，**算时间复杂度就看算法中需要执行多少次**。比如：  
**——常数阶：执行1次、8次、10次，凡是执行次数能用常数表示出来的，都记为O（1）；  
——线性阶：执行n次，则记为O（n）  
——平方阶：（一般为两层循环），假设外层循环n次，内层也循环n次，则时间复杂度为O（n^2）因为外层每循环一次，内层都要循环n次。  
那么立方阶呢？当然是O（n^3）了**。  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]  
![在这里插入图片描述][20201008091705242.png_pic_center]  
上面的尽量要熟知！  
**算法的空间复杂度：**  
算法的空间复杂度计算公式为：  
**S（n）=O(f(n))**，n为问题的规模，f(n)为语句关于n所占存储空间的函数。  
通常用“时间复杂度”☞运行时间的需求，用“空间复杂度”☞空间需求。  
如果考试让求“复杂度”，通常☞**时间复杂度。**

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center]: /images/20221123/46ac35b7ec66485eb812d5029bcff0f8.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221123/6063b7559863430b91692ef703abd5f2.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221123/cc01b863dae249ed9ca970693dbffb71.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221123/7ffb672fca594b02a42c560de1ee79a4.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221123/4678d29a52d647f396f67459d060d1b7.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ2MjE2OTUx_size_16_color_FFFFFF_t_70_pic_center 5]: /images/20221123/40ee181628644fe29dec2d1793520a7c.png
[20201008091705242.png_pic_center]: /images/20221123/2802f0fb07fe446fae0adf1c233d8423.png