数据结构与算法

文章目录

1. 复杂度

　　1.1 定义

　　1.2 表示方法

　　1.3 复杂度计算方法遵循的原则

　　　　1.3.1 复杂度与常系数无关

　　　　1.3.2 选择高阶的复杂度作为结果

　　1.4 经验数值

2. 代码优化的方法论

　　2.1 暴力解题

　　2.2 剔除掉无用的参数或者存储

　　2.3 时空转换

1. 复杂度

1.1 定义

复杂度是衡量代码运行效率的重要的度量因素。计算机执行一段程序，消耗的是计算时间和存储空间，需要衡量的就是时间复杂度和空间复杂度。

1.2 表示方法

复杂度是与计算的数据量个数n有关的函数。假设你的代码复杂度是 f(n)，那么就用个大写字母 O 和括号，把 f(n) 括起来就可以了，即 O(f(n))。

例如：

　　O(n)：表示计算的个数n与复杂度线性相关

　　O(_logn)：表示计算的个数n与复杂度对数相关

1.3 复杂度计算方法遵循的原则

1.3.1 复杂度与常系数无关

O(2n) = O(n) + O(n)，复杂度最终还是记作O(n)。

1.3.2 选择高阶的复杂度作为结果

O(n² + n) = O(n²) + O(n)，随着n的增大，n²增大的幅度要远远大于n，所以最终复杂度记为O(n²)。

注：O(1)表示一个特殊的复杂度

1.4 经验数值

2. 代码优化的方法论

2.1 暴力解题

暴力解法即不计时间和空间资源的消耗，把题目做出来。

2.2 剔除掉无用的参数或者存储

2.3 时空转换

代码执行过程计算机的内存空间不够，可以采购更高性能的计算机；但消耗的的时间则是无法弥补的，所以说空间是廉价的，时间是无价的。所以我们需要将时间复杂度向空间复杂度进行转换。具体方式是采用更复杂的数据结构，进行时间复杂度向空间复杂度的转换。

数据结构与算法

原文：https://www.cnblogs.com/YLLLike/p/12937263.html