算法性能分析

偏执的太偏执、 2024-03-31 13:20 53阅读 0赞

#### 前言 ####

*  算法性能分析
 *   *  时间复杂度
     *  递归算法时间复杂度
     *   *  （1）递推求
         *  （2）Master定理求时间复杂度
         *  （3）递归树求解
 *  空间复杂度分析
 *  代码的内存消耗
 *   *  （1）内存管理方式
     *  （2）内存对齐

## 算法性能分析 ##

### 时间复杂度 ###

程序运行时间：通常会估算算法的操作单元数量来代表程序消耗的时间  
在决定使用哪些算法的时候，不是**时间复杂越低**的越好（因为简化后的时间复杂度忽略了常数项等等），要考虑**数据规模**，如果数据规模很小甚至可以用O(n^2)的算法比O(n)的更合适（在有常数项的时候）。我们说的时间复杂度都是**省略常数项系数**的，是因为一般情况下都是默认数据规模足够的大。  
O(1)常数阶 < O(logn)对数阶 < O(n)线性阶 < O(n^2)平方阶 < O(n^3)立方阶 < O(2^n)指数阶

### 递归算法时间复杂度 ###

递归算法的时间复杂度本质上是要看: **递归的次数 \* 每次递归中的操作次数**。

#### （1）递推求 ####

![在这里插入图片描述][545beabda23e493abd7502f608071f6f.png]  
![在这里插入图片描述][a18f251bbe1d4965b13cca48e82e2a8b.png]

#### （2）Master定理求时间复杂度 ####

![在这里插入图片描述][2d3698e68e4d43958185badca76c1b5f.png]  
要求a >= 1, b > 1为整数，f(n)是正函数  
![在这里插入图片描述][3eaebad0a2414031ba77773a8197ad81.png]  
规则1举例：  
![在这里插入图片描述][e91b8bdac4bc409680caf176c38841c7.png]  
规则2举例：  
![在这里插入图片描述][8b404d5743534e71b6ae9218aac28aca.png]  
![在这里插入图片描述][248937e0590646859ed928e27e2bd839.png]

#### （3）递归树求解 ####

![在这里插入图片描述][15923456596c43cb81a35e9624da4a63.png]  
**例2：**  
![在这里插入图片描述][b35c62a7c0644a02ac54a0e1ff63ed23.png]

## 空间复杂度分析 ##

空间复杂度是考虑程序**运行时占用内存的大小**，而不是可执行文件的大小。  
递归算法的空间复杂度 = **每次递归的空间复杂度 \* 递归深度**

## 代码的内存消耗 ##

### （1）内存管理方式 ###

不同的编程语言各自的内存管理方式。

*  C/C++这种内存堆空间的申请和释放完全靠自己管理
 *  Java 依赖JVM来做内存管理，不了解jvm内存管理的机制，很可能会因一些错误的代码写法而导致内存泄漏或内存溢出
 *  Python内存管理是由私有堆空间管理的，所有的python对象和数据结构都存储在私有堆空间中。程序员没有访问堆的权限，只有解释器才能操作。

### （2）内存对齐 ###

只要可以跨平台的编程语言都需要做内存对齐。C/C++、Java、Python  
为什么会有内存对齐？【面试可能会问】  
平台原因：不是所有的硬件平台都能访问任意内存地址上的任意数据，某些硬件平台只能在某些地址处取某些特定类型的数据，否则抛出硬件异常。为了同一个程序可以在多平台运行，需要内存对齐。  
硬件原因：经过内存对齐后，CPU访问内存的速度大大提升。

[545beabda23e493abd7502f608071f6f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/bd21e7a87eb947439c9de57a583cedf4.png
[a18f251bbe1d4965b13cca48e82e2a8b.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/7594bdc04cce40f5bd267cc067eaf9c9.png
[2d3698e68e4d43958185badca76c1b5f.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/3f33bc04e1014b0c978b5a96d979b860.png
[3eaebad0a2414031ba77773a8197ad81.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/1e8376ad10104a9a9d4497ea3fe7778e.png
[e91b8bdac4bc409680caf176c38841c7.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/d14fc87876ef4551b9ef9d371bfae9f0.png
[8b404d5743534e71b6ae9218aac28aca.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/99e734795c874eeca886da5230d846d6.png
[248937e0590646859ed928e27e2bd839.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/339fe748a9b7467ab38838049d53c6b4.png
[15923456596c43cb81a35e9624da4a63.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/e61bb437effb45e8bc8e271e6dbfe63b.png
[b35c62a7c0644a02ac54a0e1ff63ed23.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/31/eddc44c23d314590b01dbbe114a4c6bc.png