1.2　算法理论

算法理论的主要目的是根据算法的性能特点对其进行分类。为了方便讨论，相关概念用数学符号表示如下。

定义：给定函数f(N)，则

O(f(N))表示所有g(N)的集合，当N→∞时，|g(N)/f(N)|有上界。

Ω(f(N))表示所有g(N)的集合，当N→∞时，|g(N)/f(N)|以一个（严格的）正数作为下界。

Θ(f(N))表示所有g(N)的集合，当N→∞时，|g(N)/f(N)|既有上界，又有下界。

这些符号改编自经典分析，1976年Knuth撰写的一篇论文[21]提倡将它用于算法分析。在算法性能界限的数学表述方面，这些符号已经被广泛使用。符号O表示上界；符号Ω表示下界；符号Θ表示同时有上界和下界。

在数学中，符号O最常见的用法是表示渐近近似的相关内容。我们将在第4章讨论这种用法。在算法理论中，符号O通常用于三种目的：一是隐藏可能无关紧要或计算不便的常量；二是在描述算法运行时间的表达式中表示相对较小的“错误”项；三是限制最坏情况。如今，符号Ω和符号Θ直接与算法理论相关，不过类似的符号在数学中也有使用（见参考资料[21]）。

由于忽略了常数因素，对使用这些符号的数学结果进行推导，比寻求更精确的答案要简单。例如，自然对数和二进制对数经常出现，且由一个常数因素相关联，所以如果不要求高精确度，可以把这两个对数都用O(logN)表示。更重要的是，如果只对基本操作执行频率进行分析，我们可以说，算法的运行时间是Θ(NlogN)秒；并且，如果不需要计算出常数的精确值，则可以假设在指定的计算机上，每个操作需要恒定的时间。

习题1.1　证明 与 相等。

作为运用这些符号来研究算法性能特点的例证，我们考虑一下对数组中的数字进行排序。输入是数组中的数，这些数以任意未知的顺序排列；输出是该数组中相同的数，但按照升序排列。这是一个值得深入研究的基本问题：我们先来考虑解决这个问题的算法，然后在技术意义上，证明该算法是“最优”的。

首先，要证明著名的递归算法，即Mergesort，这样能够有效地解决排序问题。Mergesort和本书中几乎所有的算法都由Sedgewick和Wayne在参考资料[30]中进行了详细论述，所以在这里只给出简单的介绍。对各种算法、实现和应用的进一步细节有兴趣的读者，可以参考资料[6]、[11]、[17]、[18]、[19]、[20]、[26]以及其他资料。

Mergesort把数组从中间分开，对两部分（递归地）排序，然后把排好顺序的两部分合并在一起，得到排序的结果，如Java程序1.1实现的这一功能。Mergesort是著名的分治（divide-and- conquer）算法设计范例的典型代表，这类算法先（递归）解决难度较小的子问题，然后用子问题的结果来解决初始问题。我们将在本书中分析一些这样的算法，诸如Mergesort算法这样的递归结构，通过分析会很快得到其性能特点的数学表达。

为了完成合并，程序1.1使用了两个辅助数组b和c来保存子序列（为了提高效率，最好在递归方法之外声明这些数组）。通过mergesort(0,N-1)调用这一方法对数组a[0…N-1]进行排序。调用递归算法之后，数组的两部分完成排序。再把a[ ]的前半部分复制到辅助数组b[ ]，把a[ ]的后半部分复制到辅助数组c[ ]。我们增设一个“警戒标记”INFTY，它比每个辅助数组末尾的所有元素都大。当一个辅助数组已经没有元素时，“警戒标记”INFTY能够帮助另一个辅助数组将剩下的部分转移到数组a。在这些准备条件下很容易完成合并：k每取一次新的值，就把b[i]和c[j]中较小的那个元素移动到a[k]，然后相应地增加k、i或者j。

程序1.1　Mergesort

习题1.2　在某些条件下，定义“警戒标记”值可能不方便或不切实际。实现一个不用定义“警戒标记”值的Mergesort（见参考资料[26]中介绍的各种方法）。

习题1.3　实现一种Mergesort，将数组分成三个相等的部分，先对这三部分排序，然后进行三向合并。将这一Mergesort的运行时间与标准Mergesort进行比较。

在当前情况下，Mergesort是重要的方法，因为它能保证与任何排序算法一样有效率。为使这个结论更加精确，我们首先分析Mergesort运行时间的主导因素，即所用的比较次数。

定理1.1（Mergesort比较）　如果对包含N个元素的数组进行排序，则Mergesort需要使用NlgN+O(N)次比较。

证明：若CN为程序1.1排列N个元素所需的比较次数，那么排列前半部分元素的比较次数是，合并的比较次数是N（当下标k每取一次新的数值都有一次比较）。换言之，Mergesort的比较次数可由下面的递归关系准确表示

　　（1）

为得到这个递归关系的解的性质，我们考虑当N是2的幂时的情况

将方程的两边除以2n，我们发现

这证明了，当 时，；对于N的一般情况，定理可由式（1）归纳证明。实际上，准确结果是相当复杂的，它取决于N的二进制表示的性质。在第2章，我们将详细讨论如何求解这样的递归关系。

习题1.4　求能够表示的递归关系，并利用这一关系证明

习题1.5　证明。

习题1.6　分析习题1.2中提到的三向Mergesort所使用的比较次数。

对于大多数计算机而言，程序1.1所用的基本操作的相对开销与常数因子相关，因为这些操作均为一个基本指令周期的整数倍。此外，程序的整体运行时间在比较次数的常数倍范围内。因此，我们可以合理假设：Mergesort算法的运行时间在NlgN的常数倍范围内。

从理论上讲，Mergesort表明NlogN是排序问题固有性难点的“上界”。

存在一种算法，能够以与NlgN成正比的时间，将任意N-元素文件排序。

充分证明这一结论需要根据相关操作和所用的时间，谨慎构建所需的计算机模型，但其结果却是在相对宽松的假设下得出的。我们说，“排序的时间复杂度是O(NlogN)”。

习题1.7　假设Mergesort的运行时间是，其中c和d是与机器相关的常数。证明：如果我们在特定的计算机上运行这个程序，并观察到对应某一值N的运行时间是tN，那么对于2N，我们可以精确估计运行时间是，此结果与机器因素无关。

习题1.8　在一台或多台计算机上实现Mergesort，观察时的运行时间，并根据前面的习题预测时的运行时间。然后观察时的运行时间，并计算预测的准确度百分比。

这里实现Mergesort的运行时间仅仅取决于用于排序的数组中的元素个数，而不是它们的排列方式。对于许多其他排序算法而言，其运行时间是输入序列初始顺序的函数，因此运行时间会因为初始顺序的不同而产生很大的变化。一般来讲，在算法理论中，我们更关注最坏情况的性能，因为这可以体现算法的性能特点，而不再受输入的影响；在特定算法的分析中，我们最关注平均情况的性能，因为它能够提供一种方法来预测“典型”输入的算法性能。

我们总是寻求更好的算法，那么自然而然会出现一个问题：是否存在一种排序算法，它比Mergesort具有更好的渐近性能？下面源于算法理论的经典结果说明，本质上不存在这样的算法。

定理1.2（排序复杂度）　对于某些输入，任何基于比较的排序至少要进行次比较。

证明：这个结论的完整证明在参考资料[30]和[19]中。直观地看，每次比较最多能将所考虑元素的可能排列数量减少一半，根据这一事实我们可以推出结果。由于排序之前有N！种可能的排列方式，而目标是排序后仅得到其中一种排序，将N！一直除以2直至结果小于统一的数值，则比较的次数必定至少为进行除法计算的次数，即[lgN!]。根据Stirling的渐近阶乘函数能够得出该定理的结论（见定理4.3的第2个推论）。

从理论角度出发，结果表明NlogN是排序问题固有性难点的“下界”。

如果将一个N-元素的输入文件排序，那么所有基于比较的排序算法所需时间都与NlgN成正比。

这是关于一整类算法的一般说明。我们将其概括为“排序的时间复杂度是Ω(NlogN)”。这个下界很重要，因为它与定理1.1的上界相匹配，进而表明没有算法比Mergesort具有更好的渐近运行时间，在此意义上，Mergesort是最优的。我们将其概括为“排序的时间复杂度是Θ(NlogN)”。从理论角度出发，这完成了排序“问题”的“解”：已证明上界和下界是匹配的。

再次指出，这些结论在一般的假设下是成立的，尽管它们或许不像看起来那样普通。例如，结论没有提及不基于比较的排序算法。事实上，存在基于指数计算技术的排序算法（如第9章讨论的算法），这些算法以平均线性时间运行。

习题1.9　假设已知两个不同的值，N-元素数组任意元素的取值是这两个不同值之一。设计一个排序算法，使其所需时间与N成正比。

习题1.10　当从三个不同值中取值时，给出习题1.9的答案。

在定理1.1和定理1.2的证明中，我们忽略了许多关于计算机和程序正确建模的细节。算法理论的本质是构建完善的模型，可以据此评估重要问题的固有性难点，还可以研究“有效”算法，这些算法体现了匹配相应下界的上界。对于许多重要问题范畴，在渐近最坏情况性能方面，下界和上界之间仍然存在明显差距。算法理论为研究解决这类问题的新算法提供了指导。我们需要能够降低已知上界的算法，但是寻找比已知下界性能更好的算法往往难以实现（寻找那种破坏模型条件的算法或许可行，然而下界却建立在模型条件的基础之上）。

因此算法理论提供了一种方法，能够根据算法的渐近性能将算法分类。然而，（在一个常数内）近似分析的过程经常限制我们准确预测任何特定算法性能特点的能力，尽管近似分析的确拓展了理论结果的适用性。更重要的是，算法理论通常基于最坏情况分析，这样的结果可能过于悲观，而且在预测实际性能方面最劣情况分析不如平均情况分析那样实用。这对Mergesort之类的算法（其运行时间与输入关系不大）是无关紧要的，但正如我们所看到的那样，平均情况分析有助于我们认识到：有时非最优算法在实际操作中更快一些。算法原理可以帮助我们鉴别优秀的算法，但是为了更好地比较和改进算法，我们有必要完善分析。要做到这一点，我们需要关于所用特定计算机性能特点的准确知识，以及精准确定基本操作执行频率的数学技术。在本书中我们会研究这样的技术。