简介

面试现场

你正坐在一间面试室里，刚刚在白板上完成了面试官提出的问题。内心充满喜悦——这是你梦寐以求的公司，而且你觉得自己完美地解答了问题。然而，就在你以为一切顺利时，面试官紧接着问起了你的解决方案在时间或空间复杂度上的表现。你脸上茫然的表情暴露了你在分析算法时空复杂度方面的不足。在这种常见的面试场景中，大多数计算机科班出身的毕业生尚能勉强给出一个合理的回答；但对于那些缺乏系统教育背景的候选人来说，用大O（Big Oh）符号来分析算法就会变成令人尴尬的“大乌龙（big uh oh）”。

本课程的目标读者包括：编程训练营的毕业生、转行进入编程领域的职场人士，以及希望快速复习复杂度理论的资深行业从业者。课程采用通俗易懂的语言讲解业界常用的概念，刻意避免分析算法时常涉及的复杂数学推导，确保不同技术水平的读者都能理解。与此同时，对于已经牢固掌握算法与数据结构知识，或拥有计算机科学学位的学习者而言，本课程可能无法提供太多新价值。

为什么复杂度如此重要？

如果你正在完成一门课程作业，或开发一个仅有几十名用户的应用程序，你可以不必太在意解决方案的时间和空间复杂度。但一旦进入专业领域，开始编写需要满足严格SLA（服务等级协议）要求，或面向数百万用户的服务时，你所选择的算法和数据结构就变得至关重要。设计精良的软件能够优雅地扩展规模，并在性能上显著优于设计粗糙的竞品。

通常用于讲解复杂度的经典入门案例是整数排序。以下是三个使用不同排序算法实现整数排序的示例程序。

冒泡排序

1import java.util.Random;
2class Demonstration {
3
4    static int SIZE = 10000;
5    static Random random = new Random(System.currentTimeMillis());
6    static int[] input = new int[SIZE];
7  
8    public static void main( String args[] ) {
9        createTestData();
10        long start = System.currentTimeMillis();
11        bubbleSort(input);
12        long end = System.currentTimeMillis();
13        System.out.println("Time taken = " + (end - start));
14    }
15
16    static void bubbleSort(int[] input) {
17        for (int i = 0; i < SIZE; i++) {
18            for (int j = 0; j < SIZE - 1; j++) {
19                if (input[j] > input[j + 1]) {
20                    int tmp = input[j];
21                    input[j] = input[j + 1];
22                    input[j + 1] = tmp;
23                }
24            }
25        }
26    }
27
28    static void createTestData() {
29        for (int i = 0; i < SIZE; i++) {
30            input[i] = random.nextInt(10000);
31        }
32    }  
33}

归并排序

1import java.util.Random;
2class Demonstration {
3
4    static int SIZE = 5000;
5    static Random random = new Random(System.currentTimeMillis());
6    static int[] input = new int[SIZE];
7    static int[] scratch = new int[SIZE];  
8  
9    public static void main( String args[] ) {
10        createTestData();
11        long start = System.currentTimeMillis();
12        mergeSort(0, input.length - 1, input);
13        long end = System.currentTimeMillis();
14        System.out.println("Time taken = " + (end - start));
15    }
16
17    static void mergeSort(int start, int end, int[] input) {
18
19        if (start == end) {
20            return;
21        }
22
23        int mid = (start + end) / 2;
24
25        // 排序前半部分
26        mergeSort(start, mid, input);
27
28        // 排序后半部分
29        mergeSort(mid + 1, end, input);
30
31        // 合并两个已排序的数组
32        int i = start;
33        int j = mid + 1;
34        int k;
35
36        for (k = start; k <= end; k++) {
37            scratch[k] = input[k];
38        }
39
40        k = start;
41        while (k <= end) {
42
43            if (i <= mid && j <= end) {
44                input[k] = Math.min(scratch[i], scratch[j]);
45
46                if (input[k] == scratch[i]) {
47                    i++;
48                } else {
49                    j++;
50                }
51            } else if (i <= mid && j > end) {
52                input[k] = scratch[i];
53                i++;
54            } else {
55                input[k] = scratch[j];
56                j++;
57            }
58            k++;
59        }
60    }
61
62    static void createTestData() {
63        for (int i = 0; i < SIZE; i++) {
64            input[i] = random.nextInt(1000);
65        }
66    }  
67}

双轴快排（Dual Pivot Quicksort）

1import java.util.Random;
2import java.util.Arrays;
3
4class Demonstration {
5
6    static int SIZE = 5000;
7    static Random random = new Random(System.currentTimeMillis());
8    static int[] input = new int[SIZE];
9  
10    public static void main( String args[] ) {
11        createTestData();
12        long start = System.currentTimeMillis();
13        Arrays.sort(input);
14        long end = System.currentTimeMillis();
15        System.out.println("Time taken = " + (end - start));
16    }
17
18    static void createTestData() {
19        for (int i = 0; i < SIZE; i++) {
20            input[i] = random.nextInt(10000);
21        }
22    }  
23}

上述代码可在不同规模的数据集上运行。以下是基于MacBook的一些粗略测试结果（单位为毫秒）：

上述测试结果足以激励软件开发者深入理解算法性能。随着输入规模增大，冒泡排序的性能急剧下降，而另外两种算法的表现则相对稳定。我们将在下一章进一步讨论它们的性能差异。

时间与空间

细心的读者会注意到，在归并排序的代码中使用了一个额外的数组，名为scratch数组。这正是计算机科学中的经典权衡：通过增加空间使用可以降低执行时间，反之亦然。通常情况下，时间和空间呈反比关系——空间使用增加时，执行时间减少；而执行时间增加时，所需空间则可能减少。