从 Google 算法大神那 "偷学" 的复杂度分析法，真香
>点击上方“
Java Dev
” 关注<
看看你有多少好友也关注了我
天天刷算法题，面试时啃次啃次完成了一道算法题，结果面试官问你的算法时间复杂度是多少，然后我懵逼了。
平时一味的忙着刷题，结果忘记了最重要的算法工作效率。解了一道算法题但是却不知道它的时间复杂度是多少，这就相当于我们在工作中完成了一项任务，却不知道完成的质量如何，然而你的老板心中自然有一把尺子去度量每位同事工作的质量，如果你也能拥有这把尺子，是不是也可以高质量的完成工作呢。
今天我们就一起来聊聊如何评估算法的质量，掌握度量算法的尺子可以帮助我们写出高质量的算法，并且不断的去优化算法。
说了半天算法的质量，这里的质量到底指的是什么？
你是否在课本上看到过一个公式：程序 = 数据结构 + 算法，我们将程序再细化为应用程序的一个接口，评估一个接口质量的时候主要关注哪些点呢？仔细想想最主要的 2 个点是接口的响应时间和工作时占用存储资源。这俩点恰恰也是我们评估算法质量的标准，对应到算法上来说就是算法的时间复杂度和空间复杂度。
事后统计法
说到这里可能有伙伴不服气了，不就是个运行时间吗，有什么难的。我把写好的算法，准备几组输入数据，然后在本机上运行几次，算出每次的平均运行时间和平均占用内存不就好了吗。
这确实是一种办法，并且在平时的工作中也挺常见。例如调用链监控系统中的接口响应时间指标，JVM 内存占用指标就是采用这种 事后分析法
，我司框架组将统计的功能做成了一个切面封装在框架中，所有接入框架的项目都可以享受这项功能，里面可以清楚的看到每个接口在某个时间段内最大响应时间、最小响应时间、平均响应时间，95 线，99 线等指标。这种方法固然能计算出一个程序或者算法的质量，但是它存在许多不足的地方。
依赖测试环境
它严重依赖于程序运行的环境，例如你统计的时候采用的计算机型号不同，即使机器型号相同，如果它们部分构成组件不同也都有可能影响你的统计结果。
依赖于测试数据
它严重依赖于程序的输入数据，例如统计时候输入的数据规模在十万级别，但是如果数据规模提升一个数量级到百万级别，此时可能统计出来的结果就大变样了。
同时输入数据的顺序、离散程度，同样都可能成为影响算法质量统计的因素。
介于这种方法评估算法质量的不可靠性，我们在评估算法质量的时候采用大 O 统计方法，这种方法可以屏蔽掉程序运行环境和输入数据的因素，最终科学的评估出一个算法的质量。
大 O 统计法
大 O 标记法来源于德国数学家 Paul Bachmann、Edmund Landau 等人发明的一组数学标记法（也叫做渐进符号）家族，它主要被用来描述自变量趋于特定值或者无穷大时函数的限制行为，简单来说就是用来表示函数的趋势，在计算机领域里面被用分析算法效率。
我们用如下一个简单的打印数组算法来举例说明：
public void printNums(int[] arr) {
System.out.println("开始打印");
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println("结束打印");
}
我们假设计算机执行一行代码的时间固定为 t，数组的长度为 n，那么 for 循环内的打印语句会执行 n 次，循环之外的每条语句只会执行 1 次，如果我们采用 T(n) 来代表算法的运行耗时，那么可以得到如下等式：
由于 t 是常量，随着数据输入规模 n 无限增大，则 n 的增长趋势将主宰时间函数的趋势，因此我们可以将表达式中的常量忽略不计，这样的忽略不计操作不会影响到时间函数的趋势。
将表达式用大 O 标记法来转换一下，得到如下：
如上 O(n) 就代表了上面这个简单算法的渐进时间复杂度，通常称为时间复杂度。
复杂度分类
上面的算法较为简单，我们来看一个稍微复杂一点的算法，插入排序算法了解一下：
public void insertionSort(int[] arr) {
for (int i = 1; i < arr.length; i++) {
int cur = arr[i];
int j = i - 1;
while (j >= 0 && arr[j] > cur) {
arr[j + 1] = arr[j];
j--;
}
arr[j + 1] = cur;
}
}
同样依赖于上面的假设每条指令的耗时为 t，输入数据规模为 n，则外层 for 循环的语句耗时为 3nt。内部的 while 循环根据条件的是否成立可能会出现 3 种不同的耗时：
1.假如输入数据本身就是一个正序的数组，这时候 while 循环内部的代码根本不会被执行，只需要考虑 for 循环层面的耗时就可以了。
2.假如输入数据恰好是一个倒序的数组，这时候每次都会进入 while 循环，并且之前的所有数据都要向后挪动一位，这是最差的情况。
3.假如输入的数据是离散的（通常情况），这时候 while 循环的执行的次数就比较随机了，平均为最差情况的一半。
如上三种情况其实正好对应了算法时间复杂度的三种类型：
最差时间复杂度
这种情况下，输入数组倒序，while 循环每次需要挪动最多的数据，它时间复杂度为：
注意上面出现了 n 的多次幂，由于 n 的 2 次幂在 n 无限增大的时候会完全左右函数的趋势，所以计算时间复杂度的时候我们只考虑表达式中 n 的最高次幂，忽略掉较低的，因此采用大 O 标记法表示插入排序算法的时间复杂度为：
最好时间复杂度
这种情况下，数组本身正序，while 循环内部不会执行，我们可以愉快的得出 T(n) = O(n)。
平均时间复杂度
这种情况下，while 循环内的执行次数我们取平均值为最坏情况下的一半，同样可以得出，与最坏时间复杂段相同。
如上即为算法时间复杂度的三种类型，多数情况下我们使用最坏时间复杂度，最好和平均理解就够了。
接下来我们看看几种常见的几种复杂度
O(1)
常量级的时间复杂度指的是算法可以常量时间内结束，一般这种算法中不包含循环、递归语句，注意即使算法包含了上千行代码，仍然属于常量级算法复杂度，如下加法运算为一个案例：
public int add(int a, int b, int c) {
int tmp = a + b;
int res = tmp + c;
return res;
}
平方阶级别的时间复杂度是我们平时很常见的一类算法，例如前文中的打印一维数组的案例即为 O(n) 的时间复杂度，而假如我们要打印一个二维数据，这时候就可以将它转换为一个级别时间复杂度的算法（此处假设为 n*n 的二维数组），如下：
public void printArray(intp[][] arr) {
for (int i = 0; i < arr.length; i++) {
for (int j = 0; j < arr[i].length; j++) {
System.out.println(arr[i][j] + " ");
}
System.out.println("");
}
}
当然啦，前文中的插入排序算法的实现也是一个级别时间复杂度的算法。
对数阶时间复杂度的算法也挺常见的，例如排序算法中的快速排序、堆排序和归并排序的算法复杂度都是对数阶的。我们考虑这样一个问题，给定一个数字 n，要求依次打印出不大于 n 的所有 2 的 k 次幂的数字。
即输入为 n，输出如下：
( 其中)。
求解这道题目我们可以采用如下算法：
public void printNum(int n) {
int i = 1;
while (i <= n) {
System.out.print(i + " ")
i = i * 2;
}
}
依据前文提到的计算规则，这个算法时间复杂度基本就是 while
循环内部的时间复杂度了。我们假设 2 的 k 次幂为满足要求的最大数字，则可以知道 while
循环内部最多需要执行 k 次，那我们可以得到如下等式：
则得出，依据对数运算公式化解等式，忽略掉常量和 对数底，我们可以得出
，至此我们就得出了一个对数阶时间复杂度的算法了。
如上即为我们要介绍的常见的 3 种时间复杂度，大多数算法的时间复杂度都是由上述 3 种时间复杂度变种而来。
空间复杂度
聊完算法的时间复杂度就剩下空间复杂度了，算法的空间复杂度分析方法和时间复杂度类似，常数阶的空间占用一律称为 O(1) 的空间复杂度，例如前文中打印一维数组的算法就是 O(1) 级别空间复杂度。
此处我们可以稍作修改，将它改为一个空间复杂度为 O(n) 的算法：
public void printNums(int[] arr) {
System.out.println("开始打印");
/*注意此处仅为了展示 O(n) 空间复杂度，实际代码中不会有这样的骚操作*/
int[] arr2 = new int[arr.length];
for (int i = 0; i < arr.length; i++) {
arr2[i] = arr[i];
}
for (int i : arr) {
System.out.print(i + " ");
}
System.out.println("结束打印");
}
如上即为一个 O(n) 空间复杂度的算法，以此类推你一定已经知道了空间复杂度的计算方式，由于比较简单就不再详细探讨了。
总结
今天我们一起探讨了评估算法质量的 2 个重要指标：时间复杂度和空间复杂度。
以及如何去表述时间复杂度，大 O 标记法的由来。
其中时间复杂度总共有 3 种类型，最好时间复杂度，最坏时间复杂度，平均时间复杂度。
最后我们一起探讨了三种常见的时间复杂度：。
相信聪明的你一定已经掌握如何去评估一个算法的质量，欢迎有疑问的小伙伴留言和我一起来讨论。
谢谢观看。
往期精彩
高级 Java 面试必问的三大 IO 模型，你 get 了吗？
感谢你的阅读，我为你准备了一份《高级 Java 面试指南》，点击在看，关注公众号，回复 “
礼物
”
获取。
About The Author
