算法复杂度和大O表示法

我不是女神ヾ 2021-09-20 11:20 275阅读 0赞

### 概念 ###

算法复杂度是指算法在编写成可执行程序后，运行时所需要的资源，资源包括**时间资源**和**内存资源**。

### 时间复杂度 ###

一个算法执行所耗费的时间，从理论上是不能算出来的，必须上机运行测试才能知道。但我们不可能也没有必要对每个算法都上机测试，只需知道哪个算法花费的时间多，哪个算法花费的时间少就可以了。并且一个算法花费的时间与算法中语句的执行次数成正比例，哪个算法中语句执行次数多，它花费时间就多。一个算法中的语句执行次数称为语句频度或时间频度。记为T(n)。算法的时间复杂度是指执行算法所需要的计算工作量。

### 空间复杂度 ###

空间复杂度是指算法在计算机内执行时所需存储空间的度量。  
算法执行期间所需要的存储空间包括3个部分：

*  算法程序所占的空间；
 *  输入的初始数据所占的存储空间；
 *  算法执行过程中所需要的额外空间。
 *  在许多实际问题中，为了减少算法所占的存储空间，通常采用压缩存储技术。

### 大O表示法 ###

大O表示法用于描述算法的性能和复杂程度。当讨论大O表示法时，一般考虑的是CPU（时间的占用）。大O表示法是对算法性能的一种粗略估计，并不能够精准的反应某个算法的性能。打个比方，公司分为大公司、中等公司和小公司，而大中小就是对公司规模的粗略表示，并不能够准备的表示公司具体的大小。

###### 分析算法时，时长遇到以下几类函数 ######

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

###### 下图比较了各个大O符号表示的时间复杂度 ######

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

###### 推导大O表示法的方式 ######

1.  用常量1取代运行时间中的所有加法常量；
2.  在修改后的运行次数函数中，只保留最高阶项；
3.  如果最高存在且不为1，则去除与这个项相乘的常数；

参考链接 [https://www.jianshu.com/p/88a1c8ed6254][https_www.jianshu.com_p_88a1c8ed6254]

[知乎：算法的时间和空间复杂度][Link 1]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc1NTY3Nw_size_16_color_FFFFFF_t_70]: /images/20210812/94c7ab8ac00e40ea8b3608023aeab588.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3dlaXhpbl80Mjc1NTY3Nw_size_16_color_FFFFFF_t_70 1]: /images/20210812/a3d1820c5c334b3d927ad284855b37c7.png
[https_www.jianshu.com_p_88a1c8ed6254]: https://www.jianshu.com/p/88a1c8ed6254
[Link 1]: https://zhuanlan.zhihu.com/p/50479555