要点：数据结构与算法、复杂度、程序运行的效率

程序 = 数据结构 + 算法

数据结构

一、数据结构的定义

官方定义：无

民间定义：

• “数据结构是数据对象，以及存在于该对象的实例和组成实例的数据元素之间的各种联系。这些联系可以通过定义相关的函数来给出。” — 《数据结构、算法与应用》

• “数据结构是 ADT（抽象数据类型 Abstract Data Type）的物理实现。” — 《数据结构与算法分析》

• “数据结构（data structure）是计算机中存储、组织数据的方式。通常情况下，精心选择的数据结构可以带来最优效率的算法。” —中文维基百科

• 从自己角度认识

  在计算机中，存储和组织数据的方式。

二、数据结构在生活中应用

我们知道，计算机中数据量非常庞大，如何以高效的方式组织和存储呢?

例如：一个庞大的图书馆中存放了大量的书籍，我们不仅仅要把书放进入，还应该在合适的时候能够取出来。

图书摆放要使得两个相关操作方便实现：

• 操作 1：新书怎么插入？
• 操作 2：怎么找到某本指定的书？

图书各种摆放方式：

• 方法 1：随便放

  • 操作 1：哪里有空位放哪里。
  • 操作 2：找某本书，累死。

• 方法 2：按照书名的拼音字母顺序排放

  • 操作 1：新进一本《阿 Q 正传》， 按照字母顺序找到位置，插入。
  • 操作 2：二分查找法。

• 方法 3：把书架划分成几块区域，按照类别存放，类别中按照字母顺序

  • 操作 1：先定类别，二分查找确定位置，移出空位。
  • 操作 2：先定类别，再二分查找。

结论：

• 解决问题方法的效率，根据数据的组织方式有关。
• 计算机中存储的数据量相对于图书馆的书籍来说数据量更大，数据更加多。
• 以什么样的方式，来存储和组织我们的数据才能在使用数据时更加方便呢?
• 这就是数据结构需要考虑的问题。

三、常见的数据结构

• 数组（Aarray）
• 栈（Stack）
• 链表（Linked List）
• 图（Graph）
• 散列表（Hash）
• 队列（Queue）
• 树（Tree）
• 堆（Heap）

注意：数据结构与算法与语言无关，常见的编程语言都有直接或间接的使用上述常见的数据结构。

四、逻辑结构&物理结构的区别用法

按照视点的不同，可以把数据结构分为 逻辑结构 和 物理结构：基本的目标就是将数据及其逻辑关系存储到计算机的内存中

4.1 逻辑结构

• 是指数据对象中数据元素之间的相互关系

• 面向问题的

可具体分为以下四种关系：

A 集合结构

数据元素除了同属于一个集合外，它们之间没有其他关系

B 线性结构

数据元素之间是一对一关系

C 树型结构

数据元素之间呈现一对多关系

D 图形结构

数据元素是多对多关系

4.2 物理结构

• 是指数据的逻辑结构在计算机中的存储形式，因此也称为 存储结构

• 是面向计算机的

什么是数据

• 数据是数据元素的集合

• 那么根据物理结构的定义，实际上就是如何把数据元素存储到计算机的存储器中

什么是存储器

• 存储器主要是针对内存而言的，像硬盘，软盘，光盘等外部存储器的数据组织通常用文件结构来描述

五、顺序存储&链式存储的区别用法

数据的存储结构应正确反映数据元素之间的逻辑关系

数据元素的存储结构形式有两种：顺序存储 和 链式存储

5.1 顺序存储结构

• 是把数据元素存放在地址连续的存储单元里

• 其数据间的逻辑关系和物理关系是一致的

5.2 链式存储结构

• 是把数据元素存放在任意的存储单元里

• 这组存储单元可以是连续的

• 也可以是不连续的

算法

一、算法（Algorithm）的定义

• 一个有限指令集，每条指令的描述不依赖于语言。
• 接收一些输入（有些情况下不需要输入）。
• 产生输出。
• 一定在有限步骤之后终止。

1.1 算法的特性：

1.有穷性：算法在执行有限步骤之后，自动结束而不会出现无限循环，并且每一个步骤都在可接受的时间范围内完成。当然这里的有穷并不是纯数学意义的，而是在实际应用中合理的、可以接受的“边界”。你说你写一个算法，计算机需要算上20年，一定会结束，他在数学上是有穷的，媳妇都熬成婆了，算法的意义

就不大了。

2.确定性：算法的每一个步骤都有确定的含义，不会出现二义性(不会有歧义)。

3.可行性：算法中的所有操作都可以通过已经实现的基本操作运算执行有限次来实现。

4.输入：一个算法有零个或多个输入。当用函数描述算法时，输入往往是通过形参表示的，在它们被调用时，从主调函数获得输入值。

5.输出：一个算法有一个或多个输出，它们是算法进行信息加工后得到的结果，无输出的算法没有任何意义。当用函数描述算法时，输出多用返回值或引用类型的形参表示。

1.2 算法的设计要求

好的算法应该具有正确性、可读性、健壮性、时间效率高和存储量低的特征。

1.正确性(Correctness)：能正确的反映问题的需求，能得到正确的答案。

分以下四个层次：

• 算法程序没有语法错误；

• 算法程序对n组输入产生正确的结果；

• 算法程序对典型、苛刻、有刁难性的几组输入可以产生正确的结果；

• 算法程序对所有输入产生正确的结果；

但我们不可能逐一的验证所有的输入，因此算法的正确性在大多数情况下都不可能用程序证明，而是用数学方法证明。所以一般情况下我们把层次3作为算法是否正确的标准。

2.可读性(Readability)：算法，首先应便于人们理解和相互交流，其次才是机器可执行性。可读性强的算法有助于人们对算法的理解，而难懂的算法易于隐藏错误，且难于调试和修改。

3.健壮性(Robustness)：当输入的数据非法时，好的算法能适当地做出正确反应或进行相应处理，而不会产生一些莫名其妙的输出结果。【健壮性又叫又名鲁棒性即使用棒子粗鲁地对待他也可以执行类似于Java预料到可能出现的异常并对其进行捕获处理】

4.(高效性)时间效率高和存储量低

1.3 算法分析

算法分析的目的是看算法实际是否可行，并在同一问题存在多个算法时可进行性能上的比较，以便从中挑选出比较优的算法。

(时间效率)运行时间的长短和(空间效率)占用内存空间的大小是衡量算法好坏的重要因素。

衡量算法时间效率的方法主要有两类：事后统计法和事前分析估算法。

二、算法通俗理解

• Algorithm 这个单词本意就是解决问题的办法/步骤逻辑。
• 数据结构的实现，离不开算法。

三、算法案例

假如上海和杭州之间有一条高架线，高架线长度是 1,000,000 米，有一天高架线中有其中一米出现了故障，请你想出一种算法，可以快速定位到处问题的地方。

• 线性查找

  • 从上海的起点开始一米一米的排查，最终一定能找到出问题的线段。
  • 但是如果线段在另一头，我们需要排查 1,000,000 次，这是最坏的情况，平均需要 500,000 次。

• 二分查找

  • 从中间位置开始排查，看一下问题出在上海到中间位置，还是中间到杭州的位置。
  • 查找对应的问题后，再从中间位置分开，重新锁定一般的路程。
  • 最坏的情况，需要多少次可以排查完呢? 最坏的情况是 20 次就可以找到出问题的地方。
  • 怎么计算出来的呢? log(1000000, 2)，以 2 位底，1000000 的对数 ≈ 20。

结论：
你会发现，解决问题的办法有很多，但是好的算法对比于差的算法，效率天壤之别。

复杂度

一、如何衡量程序运行的效率

当你在大数据环境中开发代码时，你一定遇到过程序执行好几个小时、甚至好几天的情况，或者是执行过程中电脑几乎死机的情况：

• 如果这个效率低下的系统是离线的，那么它会让我们的开发周期、测试周期变得很长。

• 如果这个效率低下的系统是在线的，那么它随时具有时间爆炸或者内存爆炸的可能性。

因此，衡量代码的运行效率对于一个工程师而言，是一项非常重要的基本功。本课时我们就来学习程序运行效率相关的度量方法。

二、复杂度是什么

2.1 定义

复杂度是衡量代码运行效率的重要度量因素。在介绍复杂度之前，有必要先看一下复杂度和计算机实际任务处理效率的关系，从而了解降低复杂度的必要性。

计算机通过一个个程序去执行计算任务，也就是对输入数据进行加工处理，并最终得到结果的过程。每个程序都是由代码构成的。可见，编写代码的核心就是要完成计算。但对于同一个计算任务，不同计算方法得到结果的过程复杂程度是不一样的，这对你实际的任务处理效率就有了非常大的影响。

举个例子，你要在一个在线系统中实时处理数据。假设这个系统平均每分钟会新增 300M 的数据量。如果你的代码不能在 1 分钟内完成对这 300M 数据的处理，那么这个系统就会发生时间爆炸和空间爆炸。表现就是，电脑执行越来越慢，直到死机。因此，我们需要讲究合理的计算方法，去通过尽可能低复杂程度的代码完成计算任务。

2.2 衡量复杂度

那提到降低复杂度，我们首先需要知道怎么衡量复杂度。而在实际衡量时，我们通常会围绕以下2 个维度进行。

首先，这段代码消耗的资源是什么。一般而言，代码执行过程中会消耗计算时间和计算空间，那需要衡量的就是时间复杂度和空间复杂度。

举一个实际生活中的例子。某个十字路口没有建立立交桥时，所有车辆通过红绿灯分批次行驶通过。当大量汽车同时过路口的时候，就会分别消耗大家的时间。但建了立交桥之后，所有车辆都可以同时通过了，因为立交桥的存在，等于是消耗了空间资源，来换取了时间资源。

其次，这段代码对于资源的消耗是多少。我们不会关注这段代码对于资源消耗的绝对量，因为不管是时间还是空间，它们的消耗程度都与输入的数据量高度相关，输入数据少时消耗自然就少。为了更客观地衡量消耗程度，我们通常会关注时间或者空间消耗量与输入数据量之间的关系。

时间复杂度

定义：时间复杂度所需消耗的时间即基本操作执行次数

空间复杂度

定义：算法的空间复杂度通过计算算法所需的存储空间实现，即运行完一个程序所需内存的大小

2.3 计算复杂度

复杂度是一个关于输入数据量 n 的函数。假设你的代码复杂度是 f(n)，那么就用个大写字母 O 和括号，把 f(n) 括起来就可以了，即 O(f(n))。例如，O(n) 表示的是，复杂度与计算实例的个数 n 线性相关；O(logn) 表示的是，复杂度与计算实例的个数 n 对数相关。

通常，复杂度的计算方法遵循以下几个原则：

• 首先，复杂度与具体的常系数无关，例如 O(n) 和 O(2n) 表示的是同样的复杂度。我们详细分析下，O(2n) 等于 O(n+n)，也等于 O(n) + O(n)。也就是说，一段 O(n) 复杂度的代码只是先后执行两遍 O(n)，其复杂度是一致的。

• 其次，多项式级的复杂度相加的时候，选择高者作为结果，例如 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。具体分析一下就是，O(n²)+O(n) = O(n²+n)。随着 n 越来越大，二阶多项式的变化率是要比一阶多项式更大的。因此，只需要通过更大变化率的二阶多项式来表征复杂度就可以了。

值得一提的是，O(1) 也是表示一个特殊复杂度，含义为某个任务通过有限可数的资源即可完成。此处有限可数的具体意义是，与输入数据量 n 无关。

例如，你的代码处理 10 条数据需要消耗 5 个单位的时间资源，3 个单位的空间资源。处理 1000 条数据，还是只需要消耗 5 个单位的时间资源，3 个单位的空间资源。那么就能发现资源消耗与输入数据量无关，就是 O(1) 的复杂度。

为了方便你理解不同计算方法对复杂度的影响，我们来看一个代码任务：对于输入的数组，输出与之逆序的数组。例如，输入 a=[1,2,3,4,5]，输出 [5,4,3,2,1]。

先看方法一，建立并初始化数组 b，得到一个与输入数组等长的全零数组。通过一个 for 循环，从左到右将 a 数组的元素，从右到左地赋值到 b 数组中，最后输出数组 b 得到结果。

代码如下：

1
2
3
4
5
6
7
8
9
10
11

public void s1_1() {
    int a[] = { 1, 2, 3, 4, 5 };
    int b[] = new int[5];
    for (int i = 0; i < a.length; i++) {
        b[i] = a[i];
    }
    for (int i = 0; i < a.length; i++) {
        b[a.length - i - 1] = a[i];
    }
    System.out.println(Arrays.toString(b));
}

这段代码的输入数据是 a，数据量就等于数组 a 的长度。代码中有两个 for 循环，作用分别是给b 数组初始化和赋值，其执行次数都与输入数据量相等。因此，代码的时间复杂度就是 O(n)+O(n)，也就是 O(n)。

空间方面主要体现在计算过程中，对于存储资源的消耗情况。上面这段代码中，我们定义了一个新的数组 b，它与输入数组 a 的长度相等。因此，空间复杂度就是 O(n)。

接着我们看一下第二种编码方法，它定义了缓存变量 tmp，接着通过一个 for 循环，从 0 遍历到a 数组长度的一半（即 len(a)/2）。每次遍历执行的是什么内容？就是交换首尾对应的元素。最后打印数组 a，得到结果。

代码如下：

1
2
3
4
5
6
7
8
9
10

public void s1_2() {
    int a[] = { 1, 2, 3, 4, 5 };
    int tmp = 0;
    for (int i = 0; i < (a.length / 2); i++) {
        tmp = a[i];
        a[i] = a[a.length - i - 1];
        a[a.length - i - 1] = tmp;
	}
        System.out.println(Arrays.toString(a));
}

这段代码包含了一个 for 循环，执行的次数是数组长度的一半，时间复杂度变成了 O(n/2)。根据复杂度与具体的常系数无关的性质，这段代码的时间复杂度也就是 O(n)。

空间方面，我们定义了一个 tmp 变量，它与数组长度无关。也就是说，输入是 5 个元素的数组，需要一个 tmp 变量；输入是 50 个元素的数组，依然只需要一个 tmp 变量。因此，空间复杂度与输入数组长度无关，即 O(1)。

可见，对于同一个问题，采用不同的编码方法，对时间和空间的消耗是有可能不一样的。因此，工程师在写代码的时候，一方面要完成任务目标；另一方面，也需要考虑时间复杂度和空间复杂度，以求用尽可能少的时间损耗和尽可能少的空间损耗去完成任务。

三、时间复杂度与代码结构的关系

从本质来看，时间复杂度与代码的结构有着非常紧密的关系；而空间复杂度与数据结构的设计有关，关于这一点我们会在下一讲进行详细阐述。接下来我先来系统地讲一下时间复杂度和代码结构的关系。

例 1，定义了一个数组 a = [1, 4, 3]，查找数组 a 中的最大值，代码如下：

1
2
3
4
5
6
7
8
9
10

public void s1_3() {
    int a[] = { 1, 4, 3 };
    int max_val = -1;
    for (int i = 0; i < a.length; i++) {
        if (a[i] > max_val) {
            max_val = a[i];
        }
    }
    System.out.println(max_val);
}

这个例子比较简单，实现方法就是，暂存当前最大值并把所有元素遍历一遍即可。因为代码的结构上需要使用一个 for 循环，对数组所有元素处理一遍，所以时间复杂度为 O(n)。

例2，下面的代码定义了一个数组 a = [1, 3, 4, 3, 4, 1, 3]，并会在这个数组中查找出现次数最多的那个数字：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public void s1_4() {
    int a[] = { 1, 3, 4, 3, 4, 1, 3 };
    int val_max = -1;
    int time_max = 0;
    int time_tmp = 0;
    for (int i = 0; i < a.length; i++) {
        time_tmp = 0;
        for (int j = 0; j < a.length; j++) {
            if (a[i] == a[j]) {
            time_tmp += 1;
        }
        if (time_tmp > time_max) {
            time_max = time_tmp;
            val_max = a[i];
        }
        }
    }
    System.out.println(val_max);
}

这段代码中，我们采用了双层循环的方式计算：第一层循环，我们对数组中的每个元素进行遍历；第二层循环，对于每个元素计算出现的次数，并且通过当前元素次数 time_tmp 和全局最大次数变量 time_max 的大小关系，持续保存出现次数最多的那个元素及其出现次数。由于是双层循环，这段代码在时间方面的消耗就是 n*n 的复杂度，也就是 O(n²)。

在这里，我们给出一些经验性的结论：

• 一个顺序结构的代码，时间复杂度是 O(1)。

• 二分查找，或者更通用地说是采用分而治之的二分策略，时间复杂度都是 O(logn)。这个我们会在后续课程讲到。

• 一个简单的 for 循环，时间复杂度是 O(n)。

• 两个顺序执行的 for 循环，时间复杂度是 O(n)+O(n)=O(2n)，其实也是 O(n)。

• 两个嵌套的 for 循环，时间复杂度是 O(n²)。

有了这些基本的结论，再去分析代码的时间复杂度将会轻而易举。

四、降低时间复杂度的必要性

很多新手的工程师，对降低时间复杂度并没有那么强的意识。这主要是在学校或者实验室中，参加的课程作业或者科研项目，普遍都不是实时的、在线的工程环境。

实际的在线环境中，用户的访问请求可以看作一个流式数据。假设这个数据流中，每个访问的平均时间间隔是 t。如果你的代码无法在 t 时间内处理完单次的访问请求，那么这个系统就会一波未平一波又起，最终被大量积压的任务给压垮。这就要求工程师必须通过优化代码、优化数据结构，来降低时间复杂度。

为了更好理解，我们来看一些数据。假设某个计算任务需要处理 10 万 条数据。你编写的代码：

• 如果是 O(n²) 的时间复杂度，那么计算的次数就大概是 100 亿次左右。

• 如果是 O(n)，那么计算的次数就是 10 万 次左右。

• 如果这个工程师再厉害一些，能在 O(log n) 的复杂度下完成任务，那么计算的次数就是 17 次左右（log 100000 = 16.61，计算机通常是二分法，这里的对数可以以 2 为底去估计）。

数字是不是一下子变得很悬殊？通常在小数据集上，时间复杂度的降低在绝对处理时间上没有太多体现。但在当今的大数据环境下，时间复杂度的优化将会带来巨大的系统收益。而这是优秀工程师必须具备的工程开发基本意识。

五、时间复杂度与空间复杂度的转换

你面试的过程中，常常会遇到考察手写代码的场景，通常面试官会追问：“这段代码的时间复杂度或者空间复杂度，是否还有降低的可能性？”如果没有经过专门的学习或训练，应聘者只能在各种漫无目的的尝试中去寻找答案。

别忘了，代码效率优化就是要将可行解提高到更优解，最终目标是：要采用尽可能低的时间复杂度和空间复杂度，去完成一段代码的开发。

5.1 时间昂贵、空间廉价

一段代码会消耗计算时间、资源空间，从而产生时间复杂度和空间复杂度，那么你是否尝试过将时间复杂度和空间复杂进行下对比呢？其实对比过后，你就会发现一个重要的现象。

假设一段代码经过优化后，虽然降低了时间复杂度，但依然需要消耗非常高的空间复杂度。 例如，对于固定数据量的输入，这段代码需要消耗几十 G 的内存空间，很显然普通计算机根本无法完成这样的计算。如果一定要解决的话，一个最简单粗暴的办法就是，购买大量的高性能计算机，来弥补空间性能的不足。

反过来，假设一段代码经过优化后，依然需要消耗非常高的时间复杂度。 例如，对于固定数据量的输入，这段代码需要消耗 1 年的时间去完成计算。如果在跑程序的 1 年时间内，出现了断电、断网或者程序抛出异常等预期范围之外的问题，那很可能造成 1 年时间浪费的惨重后果。很显然，用 1 年的时间去跑一段代码，对开发者和运维者而言都是极不友好的。

这告诉我们一个什么样的现实问题呢？代码效率的瓶颈可能发生在时间或者空间两个方面。如果是缺少计算空间，花钱买服务器就可以了。这是个花钱就能解决的问题。相反，如果是缺少计算时间，只能投入宝贵的人生去跑程序。即使你有再多的钱、再多的服务器，也是毫无用处。相比于空间复杂度，时间复杂度的降低就显得更加重要了。因此，你会发现这样的结论：空间是廉价的，而时间是昂贵的。

5.2 数据结构连接时空

假定在不限制时间、也不限制空间的情况下，你可以完成某个任务的代码的开发。这就是通常我们所说的暴力解法，更是程序优化的起点。

例如，如果要在 100 以内的正整数中，找到同时满足以下两个条件的最小数字：

• 能被 3 整除；

• 除 5 余 2。

最暴力的解法就是，从 1 开始到 100，每个数字都做一次判断。如果这个数字满足了上述两个条件，则返回结果。这是一种不计较任何时间复杂度或空间复杂度的、最直观的暴力解法。

当你有了最暴力的解法后，就需要用上一讲的方法评估当前暴力解法的复杂度了。如果复杂度比较低或者可以接受，那自然万事大吉。可如果暴力解法复杂度比较高的话，那就要考虑采用程序优化的方法去降低复杂度了。

为了降低复杂度，一个直观的思路是：梳理程序，看其流程中是否有无效的计算或者无效的存储。

我们需要从时间复杂度和空间复杂度两个维度来考虑。常用的降低时间复杂度的方法有递归、二分法、排序算法、动态规划等，这些知识我们都会在后续逐一学习。而降低空间复杂度的方法，就要围绕数据结构做文章了。

降低空间复杂度的核心思路就是，能用低复杂度的数据结构能解决问题，就千万不要用高复杂度的数据结构。

经过了前面剔除无效计算和存储的处理之后，如果程序在时间和空间等方面的性能依然还有瓶颈，又该怎么办呢？前面我们提到过，空间是廉价的，最不济也是可以通过购买更高性能的计算机进行解决的。然而时间是昂贵的，如果无法降低时间复杂度，那系统的效率就永远无法得到提高。

这时候，开发者们想到这样的一个解决思路。如果可以通过某种方式，把时间复杂度转移到空间复杂度的话，就可以把无价的东西变成有价了。这种时空转移的思想，在实际生活中也会经常遇到。

例如，马路上的十字路口，所有车辆在通过红绿灯时需要分批次通行。这样，就消耗了所有车辆的通行时间。如果要降低这里的时间损耗，人们就想到了修建立交桥。修建立交桥后，每个可能的转弯或直行的行进路线，都有专属的一条公路支持。这样，车辆就不需要全部去等待红绿灯分批通行了。最终，实现了用空间换取时间。

其实，程序开发也是可以借鉴这里的思想的。在程序开发中，连接时间和空间的桥梁就是数据结构。对于一个开发任务，如果你能找到一种高效的数据组织方式，采用合理的数据结构的话，那就可以实现时间复杂度的再次降低。同样的，这通常会增加数据的存储量，也就是增加了空间复杂度。

以上就是程序优化的最核心的思路，也是这个专栏的整体框架。我们简单梳理如下：

• 第一步，暴力解法。在没有任何时间、空间约束下，完成代码任务的开发。

• 第二步，无效操作处理。将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。

• 第三步，时空转换。设计合理数据结构，完成时间复杂度向空间复杂度的转移。

5.3 降低复杂度的案例

有了如上的方法论，给出几个例子，帮助你加深理解。

第 1 个例子，假设有任意多张面额为 2 元、3 元、7 元的货币，现要用它们凑出 100 元，求总共有多少种可能性。假设工程师小明写了下面的代码：

1
2
3
4
5
6
7
8
9
10
11
12
13

public void s2_1() {
    int count = 0;
    for (int i = 0; i <= (100 / 7); i++) {
        for (int j = 0; j <= (100 / 3); j++) {
            for (int k = 0; k <= (100 / 2); k++) {
                if (i * 7 + j * 3 + k * 2 == 100) {
                    count += 1;
                }
            }
        }
    }
    System.out.println(count);
}`

在这段代码中，使用了 3 层的 for 循环。从结构上来看，是很显然的 O( n³ ) 的时间复杂度。然而，仔细观察就会发现，代码中最内层的 for 循环是多余的。因为，当你确定了要用 i 张 7 元和 j 张 3 元时，只需要判断用有限个 2 元能否凑出 100 - 7* i - 3* j 元就可以了。因此，代码改写如下：

1
2
3
4
5
6
7
8
9
10
11

public void s2_2() {
    int count = 0;
    for (int i = 0; i <= (100 / 7); i++) {
        for (int j = 0; j <= (100 / 3); j++) {
            if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) {
                count += 1;
            }
        }
    }
    System.out.println(count);
}

经过改造后，代码的结构由 3 层 for 循环，变成了 2 层 for 循环。很显然，时间复杂度就变成了O(n²) 。这样的代码改造，就是利用了方法论中的步骤二，将代码中的无效计算、无效存储剔除，降低时间或空间复杂度。

再看第二个例子。查找出一个数组中，出现次数最多的那个元素的数值。例如，输入数组 a = [1,2,3,4,5,5,6 ] 中，查找出现次数最多的数值。从数组中可以看出，只有 5 出现了 2 次，其余都是 1 次。显然 5 出现的次数最多，则输出 5。

工程师小明的解决方法是，采用两层的 for 循环完成计算。第一层循环，对数组每个元素遍历。第二层循环，则是对第一层遍历的数字，去遍历计算其出现的次数。这样，全局再同时缓存一个出现次数最多的元素及其次数就可以了。具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

public void s2_3() {
    int a[] = { 1, 2, 3, 4, 5, 5, 6 };
    int val_max = -1;
    int time_max = 0;
    int time_tmp = 0;
    for (int i = 0; i < a.length; i++) {
        time_tmp = 0;
        for (int j = 0; j < a.length; j++) {
            if (a[i] == a[j]) {
            time_tmp += 1;
        }
            if (time_tmp > time_max) {
                time_max = time_tmp;
                val_max = a[i];
            }
        }
    }
    System.out.println(val_max);
}

在这段代码中，小明采用了两层的 for 循环，很显然时间复杂度就是 O(n²)。而且代码中，几乎没有冗余的无效计算。如果还需要再去优化，就要考虑采用一些数据结构方面的手段，来把时间复杂度转移到空间复杂度了。

我们先想象一下，这个问题能否通过一次 for 循环就找到答案呢？一个直观的想法是，一次循环的过程中，我们同步记录下每个元素出现的次数。最后，再通过查找次数最大的元素，就得到了结果。

具体而言，定义一个 k-v 结构的字典，用来存放元素-出现次数的 k-v 关系。那么首先通过一次循环，将数组转变为元素-出现次数的一个字典。接下来，再去遍历一遍这个字典，找到出现次数最多的那个元素，就能找到最后的结果了。

具体代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

public void s2_4() {
    int a[] = { 1, 2, 3, 4, 5, 5, 6 };
    Map<Integer, Integer> d = new HashMap<>();
    for (int i = 0; i < a.length; i++) {
        if (d.containsKey(a[i])) {
            d.put(a[i], d.get(a[i]) + 1);
        } else {
            d.put(a[i], 1);
        }
    }
    int val_max = -1;
    int time_max = 0;
    for (Integer key : d.keySet()) {
        if (d.get(key) > time_max) {
            time_max = d.get(key);
            val_max = key;
        }
    }
    System.out.println(val_max);
}

我们来计算下这种方法的时空复杂度。代码结构上，有两个 for 循环。不过，这两个循环不是嵌套关系，而是顺序执行关系。其中，第一个循环实现了数组转字典的过程，也就是 O(n) 的复杂度。第二个循环再次遍历字典找到出现次数最多的那个元素，也是一个 O(n) 的时间复杂度。

因此，总体的时间复杂度为 O(n) + O(n)，就是 O(2n)，根据复杂度与具体的常系数无关的原则，也就是O(n) 的复杂度。空间方面，由于定义了 k-v 字典，其字典元素的个数取决于输入数组元素的个数。因此，空间复杂度增加为 O(n)。

这段代码的开发，就是借鉴了方法论中的步骤三，通过采用更复杂、高效的数据结构，完成了时空转移，提高了空间复杂度，让时间复杂度再次降低。

六、总结

复杂度通常包括时间复杂度和空间复杂度。在具体计算复杂度时需要注意以下几点。

（1）可以忽略加法常数

O(2n + 3) = O(2n)
（2）与最高次项相乘的常数可忽略

O(2n^2) = O(n^2)
（3） 最高次项的指数大的，函数随着 n 的增长，结果也会变得增长得更快

O(n^3) > O(n^2)
（4）判断一个算法的（时间）效率时，函数中常数和其他次要项常常可以忽略，而更应该关注主项（最高阶项）的阶数

O(2n^2) = O(n^2+3n+1)
O(n^3) > O(n^2)

它与具体的常系数无关，O(n) 和 O(2n) 表示的是同样的复杂度。

复杂度相加的时候，选择高者作为结果，也就是说 O(n²)+O(n) 和 O(n²) 表示的是同样的复杂度。

O(1) 也是表示一个特殊复杂度，即任务与算例个数 n 无关。

复杂度细分为时间复杂度和空间复杂度，其中时间复杂度与代码的结构设计高度相关；空间复杂度与代码中数据结构的选择高度相关。会计算一段代码的时间复杂度和空间复杂度，是工程师的基本功。这项技能你在实际工作中一定会用到，甚至在参加互联网公司面试的时候，也是面试中的必考内容。

七、练习题

1.评估一下，如下的代码片段，时间复杂度是多少？

1
2
3
4
5
6
7
8

for (i = 0; i < n; i++) {
    for (j = 0; j < n; j++) {
        for (k = 0; k < n; k++) {
        }
        for (m = 0; m < n; m++) {
        }
    }
}

2.在下面这段代码中，如果要降低代码的执行时间，第 4 行需要做哪些改动呢？如果做出改动后，是否降低了时间复杂度呢？

1
2
3
4
5
6
7
8
9
10
11

public void s2_2() {
    int count = 0;
    for (int i = 0; i <= (100 / 7); i++) {
        for (int j = 0; j <= (100 / 3); j++) {
            if ((100-i*7-j*3 >= 0)&&((100-i*7-j*3) % 2 == 0)) {
                count += 1;
            }
        }
    }
    System.out.println(count);
}

提示，第 4 行代码，j 需要遍历到 33。但很显然，随着 i 的变大，j 并不需要遍历到 33。例如，当 i 为 9 的时候，j 最大也只能取到 12。如果 j 大于 12，则 79 + 313 > 100。不过，别忘了，即使是这样，j 的取值范围也是与 n 线性相关的。哪怕是 O(n/2)，其实时间复杂度也并没有变小。

• ← 上一篇
• 下一篇 →