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

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

文章来源: ai-wx.blog.csdn.net，作者：AI 菌，版权归原作者所有，如需转载，请联系作者。

原文链接：ai-wx.blog.csdn.net/article/details/106452718