【算法与数据结构 01】衡量程序运行效率——复杂度

╰+攻爆jí腚メ 2023-02-14 02:26 3阅读 0赞

### 文章目录 ###

*   *  1. 衡量标准
     *  2. 如何计算复杂度？
     *  3. 时间复杂度与代码结构的关系
     *  4. 优化代码的必要性

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

## 1. 衡量标准 ##

计算机通过一行行代码去完成某个任务，实际上就是对输入数据进行加工处理，并得到结果的过程。可见，编写代码的核心就是要完成计算。对于同一个计算任务，不同计算方法得到结果的过程`复杂程度`是不一样的，对应的`代码运行效率`也不一样。

因此，复杂度是是衡量代码运行效率的标准。

我们再想一想，一段代码消耗的资源是什么呢？  
通常，代码在执行过程中会消耗计算时间和计算空间（内存），那需要衡量的就是`时间`复杂度和`空间`复杂度。

## 2. 如何计算复杂度？ ##

复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n)，那么就用个大写字母 O 和括号，把 f(n) 括起来就可以了，即 O(f(n))。  
比如，O(n) 表示的是，复杂度与计算实例的个数 n 线性相关；O(logn) 表示的是，复杂度与计算实例的个数 n 对数相关。  
通常，复杂度的计算方法遵循以下几个原则：

1.  **复杂度与具体的常系数无关**。例如 O(n) 和 O(2n) 表示的是同样的复杂度。
2.  **多项式级的复杂度相加的时候，选择高者作为结果**。例如， O(n²+n)=O(n²)+O(n) =O(n²)。
3.  **O(1)表示常数复杂度**。即复杂度与输入量n无关，是一个定值。

## 3. 时间复杂度与代码结构的关系 ##

从本质来看，时间复杂度与`代码的结构`有着非常紧密的关系；空间复杂度与`数据结构`的设计有关。  
下面，总结了一些代码结构与时间复杂度的关系：

*  一个顺序结构的代码，时间复杂度是 O(1)。
 *  二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)。
 *  一个简单的 for 循环，时间复杂度是 O(n)。
 *  两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)。
 *  两个嵌套的 for 循环，时间复杂度是 O(n²)。

## 4. 优化代码的必要性 ##

通常在小数据集上，时间复杂度的降低在绝对处理时间上没有太多体现。但在当今的大数据环境下，时间复杂度的优化将会带来巨大的系统收益。  
假设某个计算任务需要处理 10万 条数据。你编写的代码：

*  如果是 O(n²) 的时间复杂度，那么计算的次数就大概是 100 亿次左右。
 *  如果是 O(n)，那么计算的次数就是 10万 次左右。
 *  如果是O(log n) 的复杂度，那么计算的次数就是 17 次左右（log 100000 = 16.61，计算机通常是二分法，这里的对数可以以 2 为底去估计）

可见，降低时间复杂度，能大大降低计算机计算次数，从而节省了很多处理时间。

参考链接：https://kaiwu.lagou.com/course/courseInfo.htm?courseId=185\#/detail/pc?id=3339