算法分析的正确姿势

算法| 2016-05-20

[本专题会对常见的数据结构及相应算法进行分析与总结，并会在每个系列的博文中提供几道相关的一线互联网企业面试/笔试题来巩固所学及帮助我们查漏补缺。项目地址：https://github.com/absfree/Algo。由于个人水平有限，叙述中难免存在不清晰准确的地方，希望大家可以指正，谢谢大家：）]

一、前言

在进一步学习数据结构与算法前，我们应该先掌握算法分析的一般方法。算法分析主要包括对算法的时空复杂度进行分析，但有些时候我们更关心算法的实际运行性能如何，此外，算法可视化是一项帮助我们理解算法实际执行过程的实用技能，在分析一些比较抽象的算法时，这项技能尤为实用。在在本篇博文中，我们首先会介绍如何通过设计实验来量化算法的实际运行性能，然后会介绍算法的时间复杂度的分析方法，我们还会介绍能够非常便捷的预测算法性能的倍率实验。当然，在文章的末尾，我们会一起来做几道一线互联网的相关面试/笔试题来巩固所学，达到学以致用。

二、算法分析的一般方法

1. 量化算法的实际运行性能

在介绍算法的时空复杂度分析方法前，我们先来介绍以下如何来量化算法的实际运行性能，这里我们选取的衡量算法性能的量化指标是它的实际运行时间。通常这个运行时间与算法要解决的问题规模相关，比如排序100万个数的时间通常要比排序10万个数的时间要长。所以我们在观察算法的运行时间时，还要同时考虑它所解决问题的规模，观察随着问题规模的增长，算法的实际运行时间时怎样增长的。这里我们采用算法（第4版） (豆瓣)一书中的例子，代码如下：

public class ThreeSum {
    public static int count(int[] a) {
        int N = a.length;
        int cnt = 0;
        for (int i = 0; i < N; i++) {
            for (int j = i + 1; j < N; j++) {
                for (int k = j + 1; k < N; k++) {
                    if (a[i] + a[j] + a[k] == 0) {
                        cnt++;
                    }
                }
            }
        }
        return cnt;
    }
    
    public static void main(String[] args) {
        int[] a = StdIn.readAllInts();
        StdOut.println(count(a));
    }
}

以上代码用到的StdIn和StdOut这两个类都在这里：https://github.com/absfree/Algo。我们可以看到，以上代码的功能是统计标准一个int[]数组中的所有和为0的三整数元组的数量。采用的算法十分直接，就是从头开始遍历数组，每次取三个数，若和为0，则计数加一，最后返回的计数值即为和为0的三元组的数量。这里我们采取含有整数数量分别为1000、2000、4000的3个文件（这些文件可以在上面的项目地址中找到），来对以上算法进行测试，观察它的运行时间随着问题规模的增长是怎样变化的。

测量一个过程的运行时间的一个直接的方法就是，在这个过程运行前后各获取一次当前时间，两者的差值即为这个过程的运行时间。当我们的过程本身需要的执行时间很短时间，这个测量方法可能会存在一些误差，但是我们可以通过执行多次这个过程再取平均数来减小以至可以忽略这个误差。下面我们来实际测量一下以上算法的运行时间，相关代码如下：

    public static void main(String[] args) {
        int[] a = In.readInts(args[0]);
        long startTime = System.currentTimeMillis();
        int count = count(a);
        long endTime = System.currentTimeMillis();
        double time = (endTime - startTime) / 1000.0;
        StdOut.println("The result is: " + count + ", and takes " + time + " seconds.");
    }

我们分别以1000、2000、4000个整数作为输入，得到的运行结果如下

The result is: 70, and takes 1.017 seconds. //1000个整数

The result is: 528, and takes 7.894 seconds. //2000个整数

The result is: 4039, and takes 64.348 seconds. //4000个整数

我们从以上结果大概可你看到，当问题的规模变为原来的2倍时，实际运行时间大约变为原来的8倍。根据这个现象我们可以做出一个猜想：程序的运行时间关于问题规模N的函数关系式为T(N) = k*(n^3).

在这个关系式中，当n变为原来的2倍时，T(N)会变为原来的8倍。那么ThreeSum算法的运行时间与问题规模是否满足以上的函数关系呢？在介绍算法时间复杂度的相关内容后，我们会回过头来再看这个问题。

2. 算法的时间复杂度分析

（1）基本概念

关于算法的时间复杂度，这里我们先简单介绍下相关的三种符号记法：

第一种叫Big O notation，它给出了运行时间的”渐进上界“，也就是算法在最坏情况下运行时间的上限。它的定义如下：对于f(n)和g(n)，若存在常数c和 N0，使得对于所有n > N0，都有 |f(n)| < c * g(n)，则称f(n)为O(g(n)。
第三种叫做Big Ω notation，它给出了运行时间的“渐进下界”，也就是算法在最坏情况下运行时间的下限。它的定义如下：对于f(n)和g(n)，若存在常数c和 N0，使得对于所有n > N0，都有|f(n)| > c * g(n)，则称f(n)为Ω(g(n))。
第三种叫Big Θ notation，它确定了运行时间的”渐进确界“。定义如下：对于f(n)和g(n)，若存在常数c和N0，对于所有n> N0，都有|f(n)| = c * g(n)，则称f(n)为Θ为Θ(g(n))。

我们在平常的算法分析中最常用到的是Big O notation。下面我们将介绍分析算法的时间复杂度的具体方法，若对Big O notation的概念还不是很了解，推荐大家看这篇文章：https://blog.jobbole.com/55184/。

（2）时间复杂度的分析方法

这部分我们将以上面的ThreeSum程序为例，来介绍一下算法时间复杂度的分析方法。为了方便阅读，这里再贴一下上面的程序：

 1     public static int count(int[] a) {
 2         int N = a.length;
 3         int cnt = 0;
 4         for (int i = 0; i < N; i++) {
 5             for (int j = i + 1; j < N; j++) {
 6                 for (int k = j + 1; k < N; k++) {
 7                     if (a[i] + a[j] + a[k] == 0) {
 8                         cnt++;
 9                     }
10                 }
11             }
12         }
13         return cnt;
14     }

在介绍时间复杂度分析方法前，我们首先来明确下算法的运行时间究竟取决于什么。直观地想，一个算法的运行时间也就是执行所有程序语句的耗时总和。然而在实际的分析中，我们并不需要考虑所有程序语句的运行时间，我们应该做的是集中注意力于最耗时的部分，也就是执行频率最高而且最耗时的操作。也就是说，在对一个程序的时间复杂度进行分析前，我们要先确定这个程序中哪些语句的执行占用的它的大部分执行时间，而那些尽管耗时大但只执行常数次（和问题规模无关）的操作我们可以忽略。我们选出一个最耗时的操作，通过计算这些操作的执行次数来估计算法的时间复杂度，下面我们来具体介绍这一过程。

首先我们看到以上代码的第1行和第2行的语句只会执行一次，因此我们可以忽略它们。然后我们看到第4行到第12行是一个三层循环，最内存的循环体包含了一个if语句。也就是说，这个if语句是以上代码中耗时最多的语句，我们接下来只需要计算if语句的执行次数即可估计出这个算法的时间复杂度。以上算法中，我们的问题规模为N（输入数组包含的元素数目），我们也可以看到，if语句的执行次数与N是相关的。我们不难得出，if语句会执行N * (N – 1) * (N – 2) / 6次，因此这个算法的时间复杂度为O(n^3)。这也印证了我们之前猜想的运行时间与问题规模的函数关系（T(n) = k * n ^ 3）。由此我们也可以知道，算法的时间复杂度刻画的是随着问题规模的增长，算法的运行时间的增长速度是怎样的。在平常的使用中，Big O notation通常都不是严格表示最坏情况下算法的运行时间上限，而是用来表示通常情况下算法的渐进性能的上限，在使用Big O notation描述算法最坏情况下运行时间的上限时，我们通常加上限定词“最坏情况“。

通过以上分析，我们知道分析算法的时间复杂度只需要两步（比把大象放进冰箱还少一步：) ）：

寻找执行次数多的语句作为决定运行时间的[关键操作];
分析关键操作的执行次数。

在以上的例子中我们可以看到，不论我们输入的整型数组是怎样的，if语句的执行次数是不变的，也就是说上面算法的运行时间与输入无关。而有些算法的实际运行时间高度依赖于我们给定的输入，关于这一问题下面我们进行介绍。

3. 算法的期望运行时间

算法的期望运行时间我们可以理解为，在通常情况下，算法的运行时间是多少。在很多时候，我们更关心算法的期望运行时间而不是算法在最坏情况下运行时间的上限，因为最坏情况和最好情况发生的概率是比较低的，我们更常遇到的是一般情况。比如说尽管快速排序算法与归并排序算法的时间复杂度都为O(nlogn)，但是在相同的问题规模下，快速排序往往要比归并排序快，因此快速排序算法的期望运行时间要比归并排序的期望时间小。然而在最坏情况下，快速排序的时间复杂度会变为O(n^2)，快速排序算法就是一个运行时间依赖于输入的算法，对于这个问题，我们可以通过打乱输入的待排序数组的顺序来避免发生最坏情况。

4. 倍率实验

下面我们来介绍一下算法（第4版） (豆瓣)一书中的“倍率实验”。这个方法能够简单有效地预测程序的性能并判断他们的运行时间大致的增长数量级。在正式介绍倍率实验前，我们先来简单介绍下“增长数量级“这一概念（同样引用自《算法》一书）：

我们用~f(N)表示所有随着N的增大除以f(N)的结果趋于1的函数。用g(N)~f(N)表示g(N) / f(N)随着N的增大趋近于1。通常我们用到的近似方式都是g(N) ~ a * f(N)。我们将f(N)称为g(N)的增长数量级。

我们还是拿ThreeSum程序来举例，假设g(N)表示在输入数组尺寸为N时执行if语句的次数。根据以上的定义，我们就可以得到g(N) ~ N ^ 3（当N趋向于正无穷时，g(N) / N^3 趋近于1）。所以g(N)的增长数量级为N^3，即ThreeSum算法的运行时间的增长数量级为N^3。

现在，我们来正式介绍倍率实验（以下内容主要引用自上面提到的《算法》一书，同时结合了一些个人理解）。首先我们来一个热身的小程序：

public class DoublingTest {
    public static double timeTrial(int N) {
        int MAX = 1000000;
        int[] a = new int[N];
        for (int i = 0; i < N; i++) {
            a[i] = StdRandom.uniform(-MAX, MAX);
        }
        long startTime = System.currentTimeMillis();
        int count = ThreeSum.count(a);
        long endTime = System.currentTimeMillis();
        double time =  (endTime - startTime) / 1000.0;
        return time;
    }
    
    public static void main(String[] args) {
        for (int N = 250; true; N += N) {
            double time = timeTrial(N);
            StdOut.printf("%7d %5.1f\n", N, time);
        }
    }
}

以上代码会以250为起点，每次讲ThreeSum的问题规模翻一倍，并在每次运行ThreeSum后输出本次问题规模和对应的运行时间。运行以上程序得到的输出如下所示：

上面的输出之所以和理论值有所出入是因为实际运行环境是复杂多变的，因而会产生许多偏差，尽可能减小这种偏差的方式就是多次运行以上程序并取平均值。有了上面这个热身的小程序做铺垫，接下来我们就可以正式介绍这个“可以简单有效地预测任意程序执行性能并判断其运行时间的大致增长数量级”的方法了，实际上它的工作基于以上的DoublingTest程序，大致过程如下：

开发一个[输入生成器]来产生实际情况下的各种可能的输入。
反复运行下面的DoublingRatio程序，直至time/prev的值趋近于极限2^b，则该算法的增长数量级约为N^b（b为常数）。

DoublingRatio程序如下：

运行倍率程序，我们可以得到如下输出：

250 0.0 2.0
500 0.1 5.5
1000 0.5 5.4
2000 3.7 7.0
4000 27.4 7.4
8000 218.0 8.0

我们可以看到，time/prev确实收敛到了8（2^3)。那么，为什么通过使输入不断翻倍而反复运行程序，运行时间的比例会趋于一个常数呢？答案是下面的[倍率定理]:

若T(N) ~ a * N^b * lgN，那么T(2N) / T(N) ~2^b。

以上定理的证明很简单，只需要计算T(2N) / T(N)在N趋向于正无穷时的极限即可。其中，“a * N^b * lgN”基本上涵盖了常见算法的增长量级（a、b为常数）。值得我们注意的是，当一个算法的增长量级为NlogN时，对它进行倍率测试，我们会得到它的运行时间的增长数量级约为N。实际上，这并不矛盾，因为我们并不能根据倍率实验的结果推测出算法符合某个特定的数学模型，我们只能够大致预测相应算法的性能（当N在16000到32000之间时，14N与NlgN十分接近）。

5. 均摊分析

考虑下我们之前在深入理解数据结构之链表中提到的ResizingArrayStack，也就是底层用数组实现的支持动态调整大小的栈。每次添加一个元素到栈中后，我们都会判断当前元素是否填满的数组，若是填满了，则创建一个尺寸为原来两倍的新数组，并把所有元素从原数组复制到新数组中。我们知道，在数组未填满的情况下，push操作的复杂度为 O(1)，而当一个push操作使得数组被填满，创建新数组及复制这一工作会使得push操作的复杂度骤然上升到O(n)。

对于上面那种情况，我们显然不能说push的复杂度是O(n)，我们通常认为push的“平均复杂度”为O(1)，因为毕竟每n个push操作才会触发一次“复制元素到新数组”，因而这n个push把这一代价一均摊，对于这一系列push中的每个来说，它们的均摊代价就是O(1)。这种记录所有操作的总成本并除以操作总数来讲成本均摊的方法叫做均摊分析（也叫摊还分析）。

三、小试牛刀之实战名企面试题

前面我们介绍了算法分析的一些姿势，那么现在我们就来学以致用，一起来解决几道一线互联网企业有关于算法分析的面试/笔试题。

【腾讯】下面算法的时间复杂度是____

int foo(int n) {

if (n <= 1) {

return 1；

}

return n * foo(n – 1);

}

看到这道题要我们分析算法时间复杂度后，我们要做的第一步便是确定关键操作，这里的关键操作显然是if语句，那么我们只需要判断if语句执行的次数即可。首先我们看到这是一个递归过程：foo会不断的调用自身，直到foo的实参小于等于1，foo就会返回1，之后便不会再执行if语句了。由此我们可以知道，if语句调用的次数为n次，所以时间复杂度为O(n)。

【京东】以下函数的时间复杂度为____

void recursive(int n, int m, int o) {

if (n <= 0) {

printf(“%d, %d\n”, m, o);

} else {

recursive(n – 1, m + 1, o);

recursive(n – 1, m, o + 1);

}

}

这道题明显要比上道题难一些，那么让我们来按部就班的解决它。首先，它的关键操作时if语句，因此我们只需判断出if语句的执行次数即可。以上函数会在n > 0的时候不断递归调用自身，我们要做的是判断在到达递归的base case（即n <= 0）前，共执行了多少次if语句。我们假设if语句的执行次数为T(n, m, o)，那么我们可以进一步得到：T(n, m, o) = T(n-1, m+1, o) + T(n-1, m, o+1) （当n > 0时）。我们可以看到base case与参数m, o无关，因此我们可以把以上表达式进一步简化为T(n) = 2T(n-1)，由此我们可得T(n) = 2T(n-1) = (2^2) * T(n-2)……所以我们可以得到以上算法的时间复杂度为O(2^n)。

【京东】如下程序的时间复杂度为____（其中m > 1，e > 0）

x = m;

y = 1;

while (x – y > e) {

x = (x + y) / 2;

y = m / x;

}

print(x);

以上算法的关键操作即while语句中的两条赋值语句，我们只需要计算这两条语句的执行次数即可。我们可以看到，当x – y > e时，while语句体内的语句就会执行，x = (x + y) / 2使得x不断变小（当y<<x时，执行一次这个语句会使x变为约原来的一半），假定y的值固定在1，那么循环体的执行次数即为~logm，而实际情况是y在每次循环体最后都会被赋值为m / x，这个值总是比y在上一轮循环中的值大，这样一来x-y的值就会更小，所以以上算法的时间复杂度为O(logm)。