数据结构与算法|绪论_计算方法及数据结构

---

下篇：第一章：线性结构

前言

为什么要学习数据结构与算法？
对于大部分的业务开发者来说，平常我们基本上都是利用现成已经封装好的接口，或者类库，加上一堆的业务逻辑来实现需求功能，很少会注意到数据结构与算法，比如说你用一个类库，你不懂得时间、空间复杂度的分析就不能感受到它的巧妙，写业务逻辑时什么时候用 AarryList 什么时候用 LinkedList，怎么让代码变得更加高效，为什么哪些很牛逼的框架能在高并发的情况下还能保持如此高的效率？学习数据结构和算法其实就是为了能够让我们有目的性的建立时间和空间复杂度，写出高质量的代码，能够设计基础框架，提升编程技能，不被行业所淘汰，而且掌握数据结构和算法之后看待问题的深度和角度都会不一样了。

---

一、数据结构

1.1 什么是数据结构

数据结构是计算机存储、组织数据的方式。数据结构是指相互之间存在一种或多种特定关系的数据元素的集合。

我听过一堂很有意思的课程，以如何在书架上摆放图书为例讲述数据结构，比如你是图书管理员，现在有几千本、几万本书要你去管理，把它们放到书架上，你会怎么做？

• 方式一：随便放
  • 这种方式放置图书的好处就是方便，哪里有空位就把书放到哪里，你放书是方便了，但是某天一个同学让你去找一本书你怎么找？从头找，一本一本的看，找到最后发现居然没这本书，然后不好意思的跟别人说你们这没这本书，这不就耽误了大家的时间了吗，你找书还累。
• 方式二：按照书名的拼音字母顺序排放
  • 这种方式放置图书的好处就是别人让你找书的时候你不再需要一本本的去遍历所有的图书了，可以采用二分法，快速的定位到你要找的书在哪，但是问题是，你每往里面插入一本书都需要将排在这边书之后的所有书都往后摞一格，这也不行啊。
• 方式三：把书架划分成几块区域，每块区域指定摆放某种类别的图书，在每种类别内，按照书名的拼音字符顺序排放
  • 这种方式相比前面两种就科学很多，首先你插入新书，先定书的类别，再二分法查找需要插入的位置，移出空位，查找书也一样，先定类别，再二分法去找书，这种方法就算方式一和方式二的中庸之选了，既不会特别难找某一本书，也不会特别难去插入一本书，但是问题是每个类别的书要分配多大空间，类别要怎么分，越细越好吗？

从上述怎么放书的例子，我们可以看到没有一种完美的方式解决这个问题，假如你管理的就几本书，方式一肯定是最佳选择，数据结构就像是摆放这些图书的方式，在特定的情况下寻找最佳的解决方式才是我们所需考虑的，也是学习数据结构的初衷。

数据结构可以简单理解为承载数据元素的容器，该容器中的数据元素之间存在一种或多种特性关系。

---

1.2 数据结构的基本概念

• 数据：是描述客观事物的数、字符以及所有能输入到计算机中并被计算机程序处理的符号集合
• 数据元素：是数据的基本单位，也就是说数据元素是组成数据的、有一定意义的基本单位，在计算机中通常作为整体处理
• 数据项：是具有独立含义的数据最小单位，也称为域

• 数据对象：是性质相同的有限个数据元素的集合，它是数据的一个子集

默认情况下，数据结构中的数据都指的是数据对象，数据结构 是指所有数据元素以及数据元素之间的关系，可以看作是互相之间存在着特定关系的数据元素集合，有时可把数据结构看成是带结构的数据元素的集合。
$$数据结构=数据对象+结构$$
数据结构中讨论的元素关系主要是相邻关系或邻接关系。

数据结构的三要素：

• 逻辑结构：数据元素之间的逻辑关系
• 存储结构：数据元素及其关系在计算机存储器的存储方式
• 数据的运算（算法）：施加在该数据上的操作

---

1.3 数据的逻辑结构

数据的逻辑结构是面向用户的，它反映数据元素之间的逻辑关系而不是物理关系，是独立于计算机的。

逻辑结构的表示：

由于数据逻辑结构是面向用户的，可以采用表格、图等容易理解的形式表示：

为了更通用的描述数据的逻辑结构，通常采用二元组表示数据的逻辑结构，如：
$$B=(D,R)$$
其中，$B$ 是一种逻辑数据结构，$D$ 是数据元素的集合，在 $D$ 上数据元素之间可能存在多种关系，$R$ 是所有关系的集合，即：
$$\begin{gathered} D=(d_i|0\le i\le n-1,n\ge 0) \\ R=(r_j|1\le j\le m,m\ge 0) \end{gathered}$$

• $R$ 中的某个关系 $r_j(1\le j\le m)$ 是序偶的集合。
• 对应 $r_j$ 中任一序偶 $<x,y>(x,y\in D)$，把 $x$ 叫作序偶的第一元素，把 $y$ 叫做序偶的第二元素，又称序偶的第一元素为第二元素的 前驱元素，称第二元素为第一元素的 后继元素。如在 $<x,y>$ 的序偶中，$x$ 为 $y$ 的前驱元素，而 $y$ 是 $x$ 的后继元素。
• 若某个元素没有前驱元素，则称该元素为 开始元素；若某个元素没有后继元素，则称该元素为 终端元素。
• 对于对称序偶，即满足这样的条件：若 $<x,y>\in r(r\in R)$，则 $<y,x>\in r(x,y\in D)$，可用圆括号代替尖括号，即 $(x,y)\in r$。

逻辑结构的类型：

• 集合：集合结构中的数据元素除了同属于一个集合外，它们之间没有其他关系。每个元素都是 “平等” 的，他们的共同属性是 “同属于一个集合”。
• 线性结构：若结构是非空的，则有且仅有一个开始元素和终端元素，并且所有元素最多只有一个前驱元素和一个后继元素。
• 树型结构：若结构是非空的，则有且仅有一个元素为开始元素（也称根节点），可以有多个终端元素，每个元素有零个或多个后继元素，除开始元素外每个元素有且仅有一个前驱元素。
• 图形结构：若结构是非空的，则每个元素可以有多个前驱元素和多个后继元素。

---

1.4 数据的存储结构

数据在计算机存储器中的存储方式就是存储结构，又称物理结构。

设计存储结构的这种映射应满足两个要求：

• 存储所有元素
• 存储数据元素的关系

数据存储结构的类型：

• 顺序存储结构：
  • 所有数据元素存储在一块连续的存储空间中
  • 通过元素的物理位置来表示元素之间的关系，也就是说逻辑上相邻的元素在物理位置上也是相邻的，所以不需要额外空间表示元素之间的逻辑关系
  • 结构简单，易于实现，但不易于修改和扩展
• 链式存储结构：
  • 数据元素存放在任意的存储单元中，这组存储单元可以是连续的，也可以是不连续的
  • 使用指针来表示元素之间的逻辑关系，通过指针的连接可以将元素连接成任意的数据结构
  • 易于修改和扩展，但需要更多的空间来存储指针
• 索引存储结构：
  • 在顺序存储结构的基础上，为数据元素建立附加的索引表，通过索引表来快速查找元素
  • 索引存储结构的查找速度较快，但需要额外的存储空间来建立索引表
• 哈希（散列）存储结构：
  • 根据元素的哈希值来计算元素的存储地址，通过哈希函数将元素的关键字映射到存储地址上
  • 哈希存储结构的查找速度非常快，但需要设计合理的哈希函数和解决哈希冲突的问题

---

1.5 数据的运算

数据的运算，也就是算法，是指在数据的逻辑结构上进行操作，包括对数据元素进行插入、删除、修改、查找和排序等操作。

将数据存放在计算机中的目的是为了实现一种或多种运算。运算包括功能描述（或运算功能）和功能实现（或运算实现），前者是基于逻辑结构的，是用户定义的，是抽象的；后者是基于存储结构的，是程序员用计算机语言或伪代码表示的，是详细的过程，其核心是设计实现某一运算功能的处理步骤，即算法设计。

同一逻辑结构可以对应多种存储结构，同样的运算，在不同的存储结构中，其实现过程是不同的。

关于数据的运算在之后的内容还会做更为详细的介绍。

---

1.6 数据结构和数据类型

数据类型 是一组性质相同的值的集合和定义在此集合上的一组操作的总称，例如 Java 中的 int、short 是整型数据类型。

数据结构 是指计算机处理的数据元素的组织形式和相互关系，而数据类型是某种程序设计语言中已实现的数据结构。

在程序设计语言提供的数据类型支持下，就可以根据从问题中抽象出来的各种数据模型，逐步构造出描述这些数据模型的各种新的数据结构。

抽象数据类型：

抽象数据类型（Abstract Data Type，ADT）是一个数学模型以及定义在该模型上的一组操作。它定义了数据的取值范围及其结构形式，以及对数据操作的集合。

抽象数据类型的特征是将使用与实现分离，从而实行封装和隐藏信息。抽象数据类型通过一种特定的数据结构在程序的某个部分得以实现，只关心在这个数据类型上的操作，而不关心数据结构具体实现。

抽象数据类型的强处在于对用户隐藏了实现细节，仅公开其接口。

抽象数据类型实质上就是对一个求解问题的形式化描述（与计算机无关），程序员可以在理解基础上实现它。
$$抽象数据类型=逻辑结构+抽象运算$$

---

二、算法

2.1 什么是算法

算法就是解决问题的步骤，例如：把大象放进冰箱，需要分几个步骤？

• 第一步：把冰箱门打开
• 第二步：把大象放进去
• 第三步：把冰箱门关上

算法（Algorithnm）是指解题方案的准确而完整的描述，是一系列解决问题的有限指令（每一条指令必须有明确的目标，不可以有歧义，在计算机处理的能力范围内，且不依赖任何一种计算机语言实现），接受一些输入（有些情况下也不需要输入）在一定步骤之后终止产出输出。

算法的五个重要特性：

• 有穷性：指算法在执行有限步骤之后，自动结束而不会出现无线循环，并且每一个步骤在可接受的时间内完成
• 确定性：对于每种情况下执行的操作，在算法中都有确定的含义，不会出现二义性，并且在任何条件下，算法都只有一条执行路径
• 可行性：算法的每条指令都是可执行的，即便人借助纸和笔都可以完成
• 输入：算法有零个或多个输入，大多数算法中输入参数是必要的，但对于简单的算法可以不需要输入
• 输出：算法至少有一个或多个输出，算法用于某种数据处理，如果没有输出，这样的算法是没有意义的，算法的输出和输入有着某些特定的关系
  

算法的描述：

• 自然语言描述
• 流程图描述
• 伪代码描述
• 程序语言描述

---

2.2 算法分析

算法的设计目标：① 正确性；② 可读性；③ 健壮性；④ 高时间性能与低存储量需求。

---

2.2.1 算法的评价指标

• 正确性：算法能够正确地执行预先规定的功能，并达到所期望的性能要求
  • 四个层次：
    • 第一层次：算法没有语法错误
    • 第二层次：对于几组输入数据能够得出满足规格说明要求的结果
    • 第三层次：对于精心选择的经典、苛刻并带有刁难性的几组输入数据能够得出满足规格说明要求的结果
    • 第四层次：对于一切合法的输入数据都能够得出满足规格说明要求的结果
• 可读性：算法要便于人们阅读、交流与调试
  • 提高可读性的方法：
    • ① 注释：通常用于版本与版本说明、方法与接口说明、重要的代码行或段落提示
    • ② 空行：类型声明之后、函数定义结束之后、函数体内，逻辑上不密切相关的语句之间
    • ③ 代码行：一行代码只做一件事，如只定义一个变量，或只写一条语句
    • ④ 变量命名：变量名称要具有确定的含义，应与其代表的内容相一致，尽量避免单个字符的变量名，除非是一次性的临时变量
• 健壮性：当输入数据非法运行环境改变时，算法能恰当地作出反应或进行处理，不会产生莫名其妙的输出结果
• 时空效率：算法的执行时间尽可能地短，占用的存储空间尽可能地少

算法分析目的：分析算法的时空效率以便改进算法性能

---

2.2.2 算法时间性能分析

分析方式：

• 事后分析统计方法：编写算法对应程序，统计其执行时间
• 事前估算分析方法：撇开上述因素，认为算法的执行时间是问题规模 $n$ 的函数

分析算法的时间复杂度

一个算法是由控制结构（顺序、分支和循环三种）和原操作（指固有数据类型的操作，如：+、-、*、/、++ 和 -- 等）构成的。算法执行时间取决于两者的综合效果。

一个算法的基本构成：

算法的执行时间取决于控制结构和原操作的综合效果。在一个算法中，执行原操作的次数越少，其执行时间也就相对地越少；执行原操作次数越多，其执行时间也就相对地越多。算法中所有原操作的执行次数成为 算法频度，这样一个算法的执行时间可以由算法频度来计量。

计算算法频度（时间复杂度） $T(n)$

假设算法的 问题规模 为 $n$，例如对 10 个整数排序，问题规模为 $n$ 就是 10。算法频度是问题规模 $n$ 的函数，用 $T(n)$ 表示。

算法执行时间大致等于 原操作所需的时间 × $T(n)$，也就是说 $T(n)$ 与算法的执行时间成正比。为此 用 $T(n)$ 表示算法的执行时间。比较不同算法的 $T(n)$ 大小得出算法执行时间的好坏。

大O复杂度表示法

算法的执行时间与每行代码的执行次数成正比，用 $T(n)=O(f(n))$ 表示，其中 $T(n)$ 表示算法执行总时间，$f(n)$ 表示每行代码执行总次数，而 $n$ 往往表示数据的规模。

$T(n)=O(f(n))$ 表示存在一个正的常数 $c$，使得当 $n\ge n_0$ 时都满足：
$$|T(n)|\le c|f(n)|$$
$f(n)$ 是 $T(n)$ 的上界，这种上界可能很多，通常取最接近的上界，即 紧凑上界，也就是求出 $T(n)$ 的最高阶，忽略其低阶项和常数系数，这样既可简化 $T(n)$ 的计算，又能比较客观反映出当 $n$ 很大时算法的时间性能。

在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，剩下的部分如果为 $f(n)$ ，那么时间复杂度为 $O(f(n))$

一般来说，一个没有循环的算法的执行时间与问题规模 $n$ 无关，记作 $O(1)$，也称作常数阶；一个只有一重循环的算法的执行时间与问题规模 $n$ 的增长呈线性增大关系，记作 $O(n)$，也称 线性阶；其余常用的算法时间复杂度还有平方阶 $O(n^2)$、立方阶 $O(n^3)$、对数阶 $O(lo{g}_{2}n)$、指数阶 $O(2^n)$ 等。

例如：选择排序 -> 一个大小为 n 的数组进行从小到大的排序

思路：在 0 ~ n-1 上寻找一个最小值，找到了就放到 0 位置上，然后再在 1 ~ n-1 上面找一个最小值放到 1 位置上，依次类推，最后就能够将数组中的顺序给排列好

代码如下：

    public static void selectionSor(int[] arr) {
        if (arr == null || arr.length < 2) {
            return;
        }

        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            for (int j = i + 1; j < arr.length; j++) {
                minIndex = arr[j] < arr[minIndex] ? j : minIndex;
            }
            swap(arr, i, minIndex);
        }
    }

    public static void swap(int[] arr, int i, int j) {
        int tmp = arr[i];
        arr[i] = arr[j];
        arr[j] = tmp;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在这样的一个过程中，首先在 0 ~ n-1位置上的每一个数，我们都得看一眼吧，第一步 for 循环中就看了 n 眼，然后看到的每一个数都要和之前找到的最小数进行对比，0~n-1个数中，一开始的数不需要比较，然后之后的数字就需要进行比较，姑且假设最坏情况下它也比较了 n 次，然后最后一步进行了 1 次交换操作，第二次循环看了 n-1 次，比较了 n-1 次，进行了 1 次交换操作 … 依次类推，它看了 n + (n-1) + (n-2) +…+ 1 次（等差数列），比较了 n + (n-1) + (n-2) +…+ 1 次（等差数列），和交换了 n 次，一共做了 an^2 + bn + c 次操作，它的时间复杂度就是根据这个表达式来着的，按照上述规则，在表达式中，只要高阶项，不要低阶项，也不要高阶项的系数，那么剩下的就是 n2，所以说选择排序的复杂度就是 O(n2)

---

2.2.2.1 常见的复杂度

1. 常数时间

若对于一个算法，$T(n)$ 的上界与输入大小无关，则称其具有常数时间，记作 $O(1)$ 时间。

比如说数组的寻址操作，它就是一个常数操作，和数组的数据量没什么关系，只是将 i 位置的数据拿出来，计算机在拿 i 处的数据时，只是计算了一个偏移量将上面的数据拿出来而已，这个操作对于计算机而言就是一个固定的时间。

int a = arr[i];
1

2. 线性时间

如果一个算法的时间复杂度为 $O(n)$ ，则称这个算法具有线性时间，或 $O(n)$ 时间。非正式地说，这意味着对于足够大的输入，运行时间增加的大小与输入成线性关系。例如：一个计算列表所有元素的和的程序，需要的时间与列表的长度成正比。

代码如下：

    public static int linear(int[] arr) {
        int sum = 0;
        for (int i = 0; i < arr.length; i++) {
            sum += arr[i];
        }
        return sum;
    }
1
2
3
4
5
6
7

3. 对数时间

若算法的 $T(n)$ = $O(logn)$，则称其具有对数时间。对数时间的算法是非常有效的，因为每增加一个输入，其所需要的额外计算时间会变小，常见的具有对数时间的算法有二叉树的相关操作和二分搜索。例如：在一个有序列表中查找某个值的位置，我们通过二分法进行查找。

代码如下：

    public static int logarithm(int[] arr,int num) {
        int left = 0;
        int right = arr.length-1;
        while (left <= right) {
            int mid = (left + right)/2;
            if (arr[mid] > num) {
                right = mid - 1;
            } else if (arr[mid] < num) {
                left = mid + 1;
            } else {
                return mid;
            }
        }
        return -1;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

在最糟糕的情况下，我们通过二分法拆分 x 次后，最后一个元素就是我们要找的元素。

4. 次方时间

$O(n^k)$ 表示 k 次方时间复杂度，一个算法的时间将会随着输入数据 n 的增长而呈现出 k 次关系增加。

代码如下：

    public static int power(int n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                sum = sum + i + j;
            }
        }
        return sum;
    }
1
2
3
4
5
6
7
8
9

上面的程序中，是个两层循环的程序，函数的执行时间和n是二次方的关系：$f(n)=n^2+2$；

对于这种类型的程序，我们可以用 $O(n^2)$表示。不过，循环嵌套除了这种两层循环之外，还会有三层、四层…k 层循环，对应的其复杂度就是 $O(n^3)$、$O(n^4)$ … $O(n^k)$。

5. 指数时间

$O(2^n)$ 表示指数复杂度，随着 n 的增加，算法的执行时间成倍增加，它是一种爆炸式增长的情况，例如：使用动态规划解决旅行商问题

什么是旅行商问题？

假设有一个旅行商人要拜访 n+1个城市，他必须选择所要走的路径，路径的限制是每个城市只能拜访一次，而且最后要回到原来出发的城市。路径的选择目标是要求得的路径长度为所有路径之中的最小值。

这个我就不再举例了，如果你想探究下这个问题可参见以下文章：

用动态规划法求解TSP问题

使用动态规划求解旅行商问题

6. 阶乘时间

若算法的T(n) =O(n!)，则称其具有阶乘时间。其中最典型的例子还是旅行商问题，不同于上一个指数时间的计算的方法，使用最暴力的穷举法得出的对应复杂度就是 O(n!)

---

2.2.2.3 常见复杂度比较

算法时间性能比较：假如求同一问题有两个算法：A 和 B，如果算法 A 的平均时间复杂度为 $O(n)$，而算法 B 的平均时间复杂度为 $O(n^2)$ ，一般情况下认为算法 A 的时间性能比算法 B 好。

在上图中，我们可以看到当 n 很小时，复杂度相差不大，但是当 n 增大时，就能看到很明显的区别：
$$O(1)<O(lo{g}_{2}n)<O(n)<O(nlo{g}_{2}n)<O(n^2)<O(n^3)<O(2^n)<O(n!)$$

---

2.2.2.4 最好、最坏和平均时间复杂度

设一个算法的输入规模为 $n$ ，$D_n$ 是所有输入的集合，任一输入 $I\in D_n$，$P(I)$ 是 $I$ 出现的概率，有
$$\sum _{I\in D_n}P(I)=1$$
$T(I)$ 是算法在输入 $I$ 下的执行时间，则算法的 平均时间复杂度 为：
$$A(n)=\sum _{I\in D_n}P(I)\times T(I)$$

所有可能的初始序列有 $m$ 个，$m=10!$

算法的最坏时间复杂度为：
W ( n ) = ∑ I ∈ D n M A X { T ( I ) } W(n)=\sum_{I \in D_{n}}^{MAX} \left \{ T(I) \right \} W(n)=I∈Dn​∑MAX​{T(I)}
算法的最好时间复杂度为：
B ( n ) = ∑ I ∈ D n M I N { T ( I ) } B(n)=\sum_{I \in D_{n}}^{MIN} \left \{ T(I) \right \} B(n)=I∈Dn​∑MIN​{T(I)}

但是什么是平均？平均复杂度是很难估算的，所以我们更关注最坏情况的复杂度。

---

2.2.3 算法空间性能分析

一个算法的存储量包括形参所占空间和临时变量所占空间，在对算法进行存储空间分析时，只考察 临时变量 所占空间。

空间复杂度是对一个算法在运行过程中临时占用的存储空间大小的量度，一般也作为问题规模 $n$ 的函数，以数量级形式给出，记作：$S(n)=O(g(n))$。其这家拍卖行 “O” 的含义与时间复杂度分析中的相同。

采用 Java 面向对象的程序设计语言实现抽象数据类型时，通常将一个抽象数据类型设计成一个 Java 类，采用类的数据变量表示数据的存储结构，将抽象运算通过类的 public 方法实现

---

2.3 什么是好的算法

一个好的算法的一般得从空间复杂度和时间复杂度综合衡量，做到 “省内存” 和 “效率高”

空间复杂度 S(n)：根据算法写成的程序在执行时占用存储单元的长度。这个长度往往与输入数据的规模有关。空间复杂度过高的算法可能导致使用的内存超限，造成程序非正常中断。

时间复杂度 T(n)：根据算法写成的程序在执行时耗费时间的长度。这个长度往往也与输入数据的规模有关。时间复杂度过高的低效算法可能导致我们在有生之年等不到运行结果。

这两个指标和要处理数据的规模，是直接相关的

以下我就例举两个例子来说明以上两个两个问题：

例1：写程序实现一个函数 printN，使得传入一个正整数为 n 的参数后，能顺序打印从 1 到 n 的全部正整数

实现一：循环实现

    public static void printN(int n) {
        for (int i = 1; i <= n; i++) {
            System.out.println(i);
        }
    }
1
2
3
4
5

实现二：递归实现

    public static void printN(int n) {
        if (n!=0) {
            printN(n-1);
            System.out.println(n);
        }
    }
1
2
3
4
5
6

从代码上看，这两种方式实现的所用的代码量都差不都，循环实现的方式还多使用了一个变量 i，那他们的效率是否一样呢？

当 n 比较小的时候，两者效率都差不多，但是当 n 比较大的时候，递归程序非正常终止掉了，因为递归的程序对空间的占用比较多，如果 n 特别大的时候计算机是吃不消的，可以来分析下这两种方式实现的程序都开辟了多少内存空间。

• 实现一：不管 n 有多大，它所占用的空间都是固定，并不会随着 n 的增长而增长，所以它的空间占用是一个常量，$T(n)=c$。
• 实现二：当传入 n 时，发现 n 不等于 0，又会去递归调用该函数本身，每调用一次就需要开辟一块内存空间，n 有多大就会开辟 n 块的内容资源，空间复杂度是 $T(n)=c\cdot n$，假设 n 是 100000，那么你计算机就得为其开辟 100000 块的内存空间导致内存溢出，程序非正常终止。

例2：写程序计算给定多项式在给定点 x 处的值

实现一：直接用代码翻译

    public static double fun1(int n, double[] a, double x) {
        double p = a[0];
        for (int i = 1; i <= n; i++) {
            p += (a[i] * Math.pow(x, i));
        }
        return p;
    }
1
2
3
4
5
6
7

实现二：巧妙的使用结合律，每一次把 x 当成公因子提出来

    public static double fun2(int n, double[] a, double x) {
        double p = a[n];
        for (int i = n; i > 0; i--) {
            p = a[i - 1] + x * p;
        }
        return p;
    }
1
2
3
4
5
6
7

那这两种方式实现的程序在效率上又会有什么差距呢？可以运行下测试他们所用的时间，我这里是让它计算同一组数据 一百万次所花费的时间为例：

测试代码如下

    public static void main(String[] args) {
        double[] a = {1.0,2.0,3.0,4.0,5.0,6.0,7.0,8.0,9.0};
        int n = a.length-1;
        double x = 8.0;

        long fun1StartTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            double v = fun1(n, a, x);
        }
        long fun1EndTime = System.currentTimeMillis();

        System.out.println("实现一运行 1000000 所用时间：" + (fun1EndTime-fun1StartTime));

        long fun2StartTime = System.currentTimeMillis();
        for (int i = 0; i < 1000000; i++) {
            double v = fun2(n, a, x);
        }
        long fun2EndTime = System.currentTimeMillis();

        System.out.println("实现二运行 1000000 所用时间：" + (fun2EndTime-fun2StartTime));

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

运行结果如下：

可以明显看到实现二的方式比实现一的方式效率高很多，同样的代码量为什么会有这么大的差距呢？

计算机在处理 加减 的效率比处理 乘除 的效率高，在处理 位运算 的效率比处理 加减 的效率高

在忽略加减运算的条件下，实现一处理了 $(n^2+n)/2$ 次乘法运算，时间复杂度 $T(n)=C\cdot n^2+C\cdot n$ ；实现二处理了 n 次乘法运算，时间复杂度 $T(n)=C\cdot n$ ，当 n 足够大的时候，实现二一定会比实现一的程序快很多。

---

下篇：第一章：线性结构