Algorithms 4 Note 1.4

1.4　算法分析

引言

我的程序会运行多长时间？为什么我的程序耗尽了所有内存？

1.4.1　科学方法

科学家用来理解自然世界的方法对于研究计算机程序的运行时间同样有效：

• 细致地观察真实世界的特点，通常还要有精确的测量；
• 根据观察结果提出假设模型；
• 根据模型预测未来的事件；
• 继续观察并核实预测的准确性；
• 如此反复直到确认预测和观察一致。

科学方法的一条关键原则是我们所设计的实验必须是可重现的，这样他人也可以自己验证假设的真实性。
所有的假设也必须是可证伪的，这样我们才能确认某个假设是错误的（并需要修正）。

再多的实验也不一定能够证明我是对的，但只需要一个实验就能证明我是错的。—- 爱因斯坦

1.4.2　观察

如何定量测量程序的运行时间？

• 第一个定量观察就是，计算性任务的困难程度可以用输入的规模来衡量。根据直觉，程序的运行时间应该随着输入规模的增长而变长，但我们每次在开发和运行一个程序时想问的问题都是运行时间的增长有多快。
• 另一个定量观察是运行时间和输入本身相对无关，它主要取决于问题规模。因此我们现在来重点研究如何更好地将问题规模和运行时间的关系量化。

1.4.2.1　举例

ThreeSum 程序。

1.4.2.2　计时器

准确测量给定程序的确切运行时间是很困难的。不过幸运的是我们一般只需要近似值就可以了。

• 我们希望能够把需要几秒钟或者几分钟就能完成的程序和需要几天、几个月甚至更长时间才能完成的程序区别开来，
• 而且我们希望知道对于同一个任务某个程序是不是比另一个程序快一倍。

因此，我们仍然需要准确的测量手段来生成实验数据，并根据它们得出并验证关于程序的运行时间和问题规模的假设。

1.4.2.3　实验数据的分析

程序在不同的计算机上的运行时间之比通常是一个常数。
尽管如此，你还是会提出更详细的问题：作为问题规模的一个函数，我的程序的运行时间是多久？

1.4.3　数学模型

D. E. Knuth 认为，尽管有许多复杂的因素影响着我们对程序的运行时间的理解，原则上我们仍然可能构造出一个数学模型来描述任意程序的运行时间。
Knuth 的基本见地很简单——一个程序运行的总时间主要和两点有关：

• 执行每条语句的耗时；(取决于计算机、Java 编译器和操作系统)
• 执行每条语句的频率。(取决于程序本身和输入)

如果对于程序的所有部分我们都知道了这些性质，可以将它们相乘并将程序中所有指令的成本相加得到总运行时间。
第一个挑战是判定语句的执行频率。

1.4.3.1　近似

这种频率分析可能会产生复杂冗长的数学表达式。用近似的方式忽略公式中那些非常复杂但幂次较低，且对最终结果的贡献无关紧要的项。
定义。我们用 $f(N)$ 表示所有随着 N 的增大除以 $f(N)$ 的结果趋近于 1 的函数。我们用 $g(N)\f(N)$ 表示 $g(N)/f(N)$ 随着 N 的增大趋近于 1。

1.4.3.2　近似运行时间

我们观察到的一个关键现象是执行最频繁的指令决定了程序执行的总时间——我们将这些指令称为程序的内循环。这种情况是很典型的：许多程序的运行时间都只取决于其中的一小部分指令。

1.4.3.3　对增长数量级的猜想

1.4.2.3 节中的实验和表 1.4.4 中的数学模型都支持以下猜想：
性质 A。ThreeSum（在 N 个数中找出三个和为 0 的整数元组的数量）的运行时间的增长数量级为 $N^3$。（在本书中，我们使用性质表示需要用实验验证的猜想。）

1.4.3.4　算法的分析

类似于性质 A 的猜想的意义很重要，因为它们将抽象世界中的一个 Java 程序和真实世界中运行它的一台计算机联系了起来。
增长数量级概念的应用使我们能够继续向前迈进一步：将程序和它实现的算法隔离开来。（ThreeSum 的运行时间的增长数量级是 $N^3$，这与它是由 Java 实现或是它运行在你的笔记本电脑上或是某人的手机上或是一台超级计算机上无关。决定这一点的主要因素是它需要检查输入中任意三个整数的所有可能组合。）
你所使用的算法（有时还要算上输入模型）决定了增长的数量级。(将算法和某台计算机上的具体实现分离开来是一个强大的概念，因为这使我们对算法性能的知识可以应用于任何计算机。实际上，经典算法的性能理论大部分都发表于数十年前，但它们仍然适用于今天的计算机。)

1.4.3.5　成本模型

我们使用了一个成本模型来评估算法的性质。这个模型定义了我们所研究的算法中的基本操作。例如，适合于 3-sum 问题的成本模型是我们访问数组元素的次数。3-sum 的暴力算法使用了 $~N^3/2$ 次数组访问来计算 N 个整数中和为 0 的整数三元组的数量。
在全书中我们都会使用某个确定的成本模型研究所讨论的算法。

1.4.3.6　总结

对于大多数程序，得到其运行时间的数学模型所需的步骤如下：

• 确定输入模型，定义问题的规模；
• 识别内循环；
• 根据内循环中的操作确定成本模型；
• 对于给定的输入，判断这些操作的执行频率。这可能需要进行数学分析——我们在本书中会在学习具体的算法时给出一些例子。

如果一个程序含有多个方法，我们一般会分别讨论它们，
例如，二分查找( BinarySearch)的输入模型是大小为 N 的数组 a[]，内循环是一个 while 循环中的所有语句，成本模型是比较操作（比较两个数组元素的值）。（3.1 节中的命题 B 详细完整地给出了 1.1 节中讨论的内容，该命题说明它所需的比较次数最多为 $lgN + 1$。）
白名单的输入模型是白名单的大小 N 和由标准输入得到的 M 个整数，且我们假设 $M >> N$，内循环是一个 while 循环中的所有语句，成本模型是比较操作（承自二分查找）。由二分查找的分析我们可以立即得到对白名单问题的分析——比较次数最多为 $M(lgN + 1)$。

在算法分析中进行数学建模是一个多产的研究领域，但它多少超出了本书的范畴。通过二分查找、归并排序和其他许多算法你仍会看到，理解特定的数学模型对于理解基础算法的运行效率是很关键的，因此我们常常会详细地证明它们或是引用经典研究中的结论。在其中，我们会遇到各种数学分析中广泛使用的函数和近似函数。

1.4.4 增长数量级的分类

我们在实现算法时使用了几种结构性的原语（普通语句、条件语句、循环、嵌套语句和方法调用），所以成本增长的数量级一般都是问题规模 N 的若干函数之一。

1.4.4.1　常数级别

运行时间的增长数量级为常数的程序完成它的任务所需的操作次数一定，因此它的运行时间不依赖于 N。

1.4.4.2 对数级别

运行时间的增长数量级为对数的程序仅比常数时间的程序稍慢。运行时间和问题规模成对数关系的程序的经典例子就是二分查找。对数的底数和增长的数量级无关，所以我们在说明对数级别时一般使用 $logN$。

1.4.4.3 线性级别

使用常数时间处理输入数据中的所有元素或是基于单个 for 循环的程序是十分常见的。此类程序的增长数量级是线性的——它的运行时间和 N 成正比。

1.4.4.4 线性对数级别

我们用线性对数描述运行时间和问题规模 N 的关系为 $NlogN$ 的程序(和之前一样，对数的底数和增长的数量级无关)。
线性对数算法的典型例子是 Merge.sort和Quick.sort

1.4.4.5　平方级别

一个运行时间的增长数量级为 N^2 的程序一般都含有两个嵌套的 for 循环，对由 N 个元素得到的所有元素对进行计算。初级排序算法 Selection.sort() 和 Insertion.sort() 都是这种类型的典型程序。

1.4.4.6 立方级别

一个运行时间的增长数量级为 $N^3$ 的程序一般都含有三个嵌套的 for 循环，对由 N 个元素得到的所有三元组进行计算。ThreeSum 就是一个典型的例子。

1.4.4.7 指数级别

在第 6 章中（也只会在第 6 章）我们将会遇到运行时间和 $2^N$ 或者更高级别的函数成正比的程序。一般我们会使用指数级别来描述增长数量级为 $b^N$ 的算法(其中 $b > 1$ 且为常数，尽管不同的 b 值得到的运行时间可能完全不同)。
指数级别的算法非常慢——不可能用它们解决大规模的问题。但指数级别的算法仍然在算法理论中有着重要的地位，因为它们看起来仍然是解决许多问题的最佳方案。

总结

以上是最常见分类，但肯定不是最全面的。算法的增长数量级可能是 $N^2logN$ 或者 $N^(3/2)$ 或者是其他类似的函数。实际上，详细的算法分析可能会用到若干个世纪以来发明的各种数学工具。
我们所学习的一大部分算法的性能特点都很简单，可以使用我们所讨论过的某种增长数量级函数精确地描述。如，归并排序所需的运行时间的增长数量级是线性对数的。简单起见，我们将这句话简写为归并排序是线性对数的。

1.4.5 设计更快的算法

学习程序的增长数量级的一个重要动力是为了帮助我们为同一个问题设计更快的算法。
怎么知道如何设计一个更快的算法呢？这个问题的答案是，我们已经讨论并使用过两个经典的算法，即归并排序和二分查找。也知道归并排序是线性对数级别的，二分查找是对数级别的。如何利用它们解决 3-sum 问题呢？

1.4.6 倍率实验

下面这种方法可以简单有效地预测任意程序的性能并判断它们的运行时间大致的增长数量级。

在有性能压力的情况下应该考虑对编写过的所有程序进行倍率实验——这是一种估计运行时间的增长数量级的简单方法，或许它能够发现一些性能问题，比如你的程序并没有想象的那样高效。

一般来说，我们可以用以下方式对程序的运行时间的增长数量级作出假设并预测它的性能。

1.4.6.1 评估它解决大型问题的可行性

你需要回答这个基本问题：“该程序能在可接受的时间内处理这些数据吗？”
了解程序的运行时间的增长数量级能够为你提供精确的信息，从而理解你能够解决的问题规模的上限。
理解诸如此类的问题，是研究性能的首要原因。没有这些知识，你将对一个程序所需的时间一无所知；而如果你有了它们，一张信封的背面就足够你计算出运行所需的时间并采取相应的行动。

1.4.6.2 评估使用更快的计算机所产生的价值

另一个基本问题是：“如果我能够得到一台更快的计算机，解决问题的速度能够加快多少？”
如果新计算机比老的快 x 倍，运行时间也将变为原来的 x 分之一。但你一般都会用新计算机来处理更大规模的问题，这将会如何影响所需的运行时间呢？同样，增长的数量级信息也正是你回答这个问题所需要的。

著名的摩尔定律告诉我们，18 个月后计算机的速度和内存容量都会翻一番，5 年后计算机的速度和内存容量都会变为现在的 10 倍。如果你使用的是平方或者立方级别的算法，摩尔定律就不适用了。进行倍率测试并检查随着输入规模的倍增前后运行时间之比是趋向于 2 而非 4 或者 8 即可验证这种情况。

1.4.7　注意事项

1.4.7.1　大常数

1.4.7.2　非决定性的内循环

1.4.7.3　指令时间

1.4.7.4　系统因素

1.4.7.5　不分伯仲

1.4.7.6　对输入的强烈依赖

1.4.7.7　多个问题参量

1.4.8　处理对于输入的依赖

对于许多问题，刚才所提到的注意事项中最突出的一个就是对于输入的依赖，因为在这种情况下程序的运行时间的变化范围可能非常大。

ThreeSum 的修改版本的运行时间的范围根据输入的不同可能在常数级别到立方级别之间，因此如果我们想要预测它的性能，就需要对它进行更加细致的分析。

1.4.8.1　输入模型

一种方法是更加小心地对我们所要解决的问题所处理的输入建模。

1.4.8.2　对最坏情况下的性能的保证

有些应用程序要求程序对于任意输入的运行时间均小于某个指定的上限。
为了提供这种性能保证，理论研究者们要从极度悲观的角度来估计算法的性能：在最坏情况下程序的运行时间是多少？（这种保守的做法对于运行在核反应堆、心脏起搏器或者刹车控制器之中的软件可能是十分必要的。）

1.4.8.3　随机化算法

为性能提供保证的一种重要方法是引入随机性。
例如，我们将在2.3 节中学习的快速排序算法（可能是使用最广泛的排序算法）在最坏情况下的性能是平方级别的，但通过随机打乱输入，根据概率我们能够保证它的性能是线性对数的。每次运行该算法，它所需的时间均不相同，但它的运行时间超过线性对数级别的可能性小到可以忽略。
例如， 3.4 节中学习的用于符号表的散列算法（同样也可能是使用最广泛的同类算法），在最坏情况下的性能是线性级别的，但根据概率我们可以保证它的运行时间是常数级别的。
这些保证并不是绝对的，但它们失效的可能性甚至小于你的电脑被闪电击中的可能性。因此，这种保证在实际中也可以用来作为最坏情况下的性能保证。

1.4.8.4　操作序列

对于许多应用来说，算法的“输入”可能并不只是数据，还包括用例所进行的一系列操作的顺序。
例如，对于一个下压栈来说，用例先压入 N 个值然后再将它们全部弹出的所得到的性能，和 N 次压入弹出的混合操作序列所得到的性能可能大不相同。

1.4.8.5　均摊分析

相应地，提供性能保证的另一种方法是通过记录所有操作的总成本并除以操作总数来将成本均摊。在这里，我们可以允许执行一些昂贵的操作，但保持所有操作的平均成本较低。这种类型分析的典型例子是我们在 1.3 节中对基于动态调整数组大小的Stack 数据结构（请见 1.3.2.5 节的算法 1.1）的研究。

1.4.9　内存

和运行时间一样，一个程序对内存的使用也和物理世界直接相关：计算机中的电路很大一部分的作用就是帮助程序保存一些值并在稍后取出它们。
在任意时刻需要保存的值越多，需要的电路也就越多。你可能知道计算机能够使用的内存上限（知道这一点的人应该比知道运行时间限制的人要多）因为你很可能已经在内存上花了不少额外的支出。
内存的使用是和实现相关的。
Java 最重要的特性之一就是它的内存分配系统。它的任务是把你从对内存的操作之中解脱出来。（显然，你肯定已经知道应该在适当的时候利用这个功能，但是你也应该（至少是大概）知道程序对内存的需求在何时会成为解决问题的障碍。）
分析内存的使用比分析程序所需的运行时间要简单得多，主要原因是它所涉及的程序语句较少（只有声明语句）且在分析中我们会将复杂的对象简化为原始数据类型，而原始数据类型的内存使用是预先定义好的，而且非常容易理解：只需将变量的数量和它们的类型所对应的字节数分别相乘并汇总即可。（例如，因为 Java 的int数据类型是$-2 147 483 648$ 到$2 147 483 647$ 之间的整数值的集合，即总数为 $2^32$ 个不同的值，典型的 Java 实现使用 32 位来表示 int 值。）
根据可用内存的总量就能够计算出保存这些值的极限数量。

1.4.9.1　对象

要知道一个对象所使用的内存量，需要将所有实例变量使用的内存与对象本身的开销（一般是 16 字节,这些开销包括一个指向对象的类的引用、垃圾收集信息以及同步信息。）相加。

另外，一般内存的使用都会被填充为8 字节（64 位计算机中的机器字）的倍数。
当我们说明一个引用所占的内存时，我们会单独说明它所指向的对象所占用的内存，因此这个内存使用总量并没有包含 String 值所使用的内存。

1.4.9.2　链表

嵌套的非静态（内部）类，例如我们的 Node 类（请见 1.3.3.1 节），还需要额外的 8 字节（用于一个指向外部类的引用）。因此，一个 Node 对象需要使用 40 字节（16 字节的对象开销，指向 Item 和 Node 对象的引用各需 8 字节，另外还有 8 字节的额外开销）。
因为 Integer 对象需要使用 24 字节，一个含有 N 个整数的基于链表的栈（请见算法 1.2）需要使用（32+64N）字节，包括 Stack 对象的 16 字节的开销，引用类型实例变量8 字节，int 型实例变量4 字节，4 个填充字节，每个元素需要 64 字节，一个Node 对象的 40 字节和一个Integer 对象的 24 字节。

1.4.9.3　数组

图 1.4.9 总结了 Java 中的各种类型的数组对内存的典型需求。
Java 中数组被实现为对象，它们一般都会因为记录长度而需要额外的内存。(一个原始数据类型的数组一般需要 24 字节的头信息（16 字节的对象开销，4 字节用于保存长度以及 4 填充字节）再加上保存值所需的内存。)
一个对象的数组就是一个对象的引用的数组，所以我们应该在对象所需的内存之外加上引用所需的内存。
二维数组是一个数组的数组（每个数组都是一个对象）。

1.4.9.4　字符串对象

我们可以用相同的方式说明 Java 的 String 类型对象所需的内存，只是对于字符串来说别名是非常常见的。
String 的标准实现含有 4 个实例变量：一个指向字符数组的引用（8 字节）和三个 int 值（各 4 字节）。

1.4.9.5　字符串的值和子字符串

1.4.10　展望

良好的性能是非常重要的。速度极慢的程序和不正确的程序一样无用，因此显然有必要在一开始就关注程序的运行成本，这能够让你大致估计出所要解决的问题的规模，而聪明的做法是时刻关注程序中的内循环代码的组成。

但在编程领域中，最常见的错误或许就是过于关注程序的性能。你的首要任务应该是写出清晰正确的代码。C.A.R. Hoare（快速排序的发明人，也是一位推动编写清晰而正确的代码的领军人物）曾将这种想法总结为：

不成熟的优化是所有罪恶之源

在编程领域中，第二常见的错误或许是完全忽略了程序的性能。较快的算法一般都比暴力算法更复杂，所以很多人宁可使用较慢的算法也不愿应付复杂的代码。但是，几行优秀的代码有时能够给你带来巨大的收益。