从 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 种类型，最好时间复杂度，最坏时间复杂度，平均时间复杂度。

最后我们一起探讨了三种常见的时间复杂度：。

相信聪明的你一定已经掌握如何去评估一个算法的质量，欢迎有疑问的小伙伴留言和我一起来讨论。

谢谢观看。

往期精彩

1 分钟看穿零拷贝技术，看不懂你打我

为什么 Java 程序员必须要懂类加载机制？

高级 Java 面试必问的三大 IO 模型，你 get 了吗？

细嚼慢咽 Java 线程池，你品你细品

分享一道美团一面的面试题，简单又细腻

final 这道送分题，你答对了吗？

面试官问我 volatile 是否存在伪共享问题？我懵逼了

Java 垃圾回收器很难？是你学的方法不对

当我们在谈论内存时，我们在谈论什么

聊聊 Java 的几把 JVM 级锁

感谢你的阅读，我为你准备了一份《高级 Java 面试指南》，点击在看，关注公众号，回复 " 礼物 "  获取。