如何评判算法好坏

算法好坏可以通过下面两个纬度进行评判：

• 时间复杂度

  评估执行程序的次数（执行时间）

• 空间复杂度

  评估执行程序所需的存储空间

时间复杂度和空间复杂度描述方式

一般用 大O表示法 来描述复杂度，表示 数据规模n 对应的复杂度。不过要注意 大O表示法 仅仅是一种粗略的分析模型，是一种估算，用来帮助我们在短时间内了解一个算法的执行效率。

时间复杂度

时间复杂度又称"渐进式时间复杂度"，用来表示代码执行时间与数据规模之间的增长关系。

时间复杂度的推倒步骤：

1. 找出算法中的基本语句

   算法中执行次数最多的那条语句就是基本语句，通常是最内层循环的循环体。

2. 计算基本语句的执行次数的数量级

   只需计算基本语句执行次数的数量级，这就意味着只要保证基本语句执行次数的函数中的最高次幂正确即可，可以忽略所有低次幂和最高次幂的系数。这样能够简化算法分析，并且使注意力集中在最重要的一点上：增长率。可以简单概括为忽略常数、系数、低阶。

3. 用大Ο记号表示算法的时间性能

   将基本语句执行次数的数量级放入大Ο记号中。

简单举几个推倒大O表达式的例子：

• =>
• =>
• =>
• =>
• =>
• =>
• =>

常见的算法时间复杂度

由小到大依次为：常量阶 < 对数阶 < 线性阶 < 线性对数阶 < 平方阶 < 立方阶 < k 方阶... < 指数阶 < 阶乘阶

空间复杂度

空间复杂度，又称"渐进空间复杂度"，用来表示代码存储空间与数据规模之间的增长关系。。

空间复杂度包含三个部分：输入数据所占的存储空间，程序本身所占的空间，算法执行过程中所需的存储空间。

我们谈的空间复杂度，一般都是在讨论第三个部分，即算法执行过程中所需的存储空间。因为前两个部分，与算法并无太大关系，是由输入数据的规模以及编译链接后生成的可执行程序的大小决定。

空间复杂度的推倒规则：

1. 当一个算法的需要的空间为一个常量，即不随被处理 数据规模n 的大小而改变时，可表示为
2. 当一个算法的需要的空间和 数据规模n 成正比，可表示为

当然像 也有，不过很少见。

如何优化算法

1. 用尽量少的存储空间
2. 用尽量少的执行步骤
3. 根据具体情况，选择空间换时间或时间换空间

参考文献

1. 大O表示法
2. 如何理解算法的空间复杂度？

---

Title: 如何评判算法好坏

Date: 2020.07.22

Author: zhangpeng

Github: https://github.com/fullstack-zhangpeng