第1章 算法在计算中的作用
什么是算法？为什么算法值得研究？相对于计算机中使用的其他技术来说算法的作用是什么？本章我们将回答这些问题。
1.1 算法
非形式地说，算法（algorithm）就是任何良定义的计算过程，该过程取某个值或值的集合作为输入并产生某个值或值的集合作为输出。这样算法就是把输入转换成输出的计算步骤的一个序列。
我们也可以把算法看成是用于求解良说明的计算问题的工具。一般来说，问题陈述说明了期望的输入/输出关系。算法则描述一个特定的计算过程来实现该输入/输出关系。
例如，我们可能需要把一个数列排成非递减序。实际上，这个问题经常出现，并且为引入许多标准的设计技术和分析工具提供了足够的理由。下面是我们关于排序问题的形式定义。
输入：n个数的一个序列〈a1,a2,…,an〉。
输出：输入序列的一个排列〈a′1,a′2,…,a′n〉，满足a′1≤a′2≤…≤a′n。
例如，给定输入序列〈31,41,59,26,41,58〉，排序算法将返回序列〈26,31,41,41,58,59〉作为输出。这样的输入序列称为排序问题的一个实例（instance）。一般来说，问题实例由计算该问题解所必需的（满足问题陈述中强加的各种约束的）输入组成。
5
因为许多程序使用排序作为一个中间步，所以排序是计算机科学中的一个基本操作。因此，已有许多好的排序算法供我们任意使用。对于给定应用，哪个算法最好依赖于以下因素：将被排序的项数、这些项已被稍微排序的程度、关于项值的可能限制、计算机的体系结构，以及将使用的存储设备的种类（主存、磁盘或者磁带）。
若对每个输入实例算法都以正确的输出停机，则称该算法是正确的，并称正确的算法解决了给定的计算问题。不正确的算法对某些输入实例可能根本不停机，也可能以不正确的回答停机。与人们期望的相反，不正确的算法只要其错误率可控有时可能是有用的。在第31章，当我们研究求大素数算法时，将看到一个具有可控错误率的算法例子。但是通常我们只关心正确的算法。
算法可以用英语说明，也可以说明成计算机程序，甚至说明成硬件设计。唯一的要求是这个说明必须精确描述所要遵循的计算过程。
算法解决哪种问题
排序绝不是已开发算法的唯一计算问题（当看到本书的厚度时，你可能觉得算法也同样多）。算法的实际应用无处不在，包括以下例子：
人类基因工程已经取得重大进展，其目标是识别人类DNA中的所有10万个基因，确定构成人类DNA的30亿个化学基对的序列，在数据库中存储这类信息并为数据分析开发工具。这些工作都需要复杂的算法。虽然对涉及的各种问题的求解超出了本书的范围，但是求解这些生物问题的许多方法采用了本书多章内容的思想，从而使得科学家能够有效地使用资源以完成任务。因为可以从实验技术中提取更多的信息，所以既能节省人和机器的时间又能节省金钱。
互联网使得全世界的人都能快速地访问与检索大量信息。借助于一些聪明的算法，互联网上的网站能够管理和处理这些海量数据。必须使用算法的问题示例包括为数据传输寻找好的路由（求解这些问题的技术在第24章给出），
6使用一个搜索引擎来快速地找到特定信息所在的网页（有关技术在第11章和第32章中）。
电子商务使得货物与服务能够以电子方式洽谈与交换，并且它依赖于像信用卡号、密码和银行结单这类个人信息的保密性。电子商务中使用的核心技术包括（第31章中包含的）公钥密码与数字签名，它们以数值算法和数论为基础。
制造业和其他商务企业常常需要按最有益的方式来分配稀有资源。一家石油公司也许希望知道在什么地方设置其油井，以便最大化其预期的利润。一位政治候选人也许想确定在什么地方花钱购买竞选广告，以便最大化赢得竞选的机会。一家航空公司也许希望按尽可能最廉价的方式把乘务员分配到班机上，以确保每个航班被覆盖并且满足政府有关乘务员调度的法规。一个互联网服务提供商也许希望确定在什么地方放置附加的资源，以便更有效地服务其顾客。所有这些都是可以用线性规划来求解的问题的例子，我们将在第29章学习这种技术。
虽然这些例子的一些细节已超出本书的范围，但是我们确实说明了一些适用于这些问题和问题领域的基本技术。我们还说明如何求解许多具体问题，包括以下问题：
给定一张交通图，上面标记了每对相邻十字路口之间的距离，我们希望确定从一个十字路口到另一个十字路口的最短道路。即使不允许穿过自身的道路，可能路线的数量也会很大。在所有可能路线中，我们如何选择哪一条是最短的？这里首先把交通图（它本身就是实际道路的一个模型）建模为一个图（第六部分和附录B将涉及这个概念），然后寻找图中从一个顶点到另一个顶点的最短路径。第24章将介绍如何有效地求解这个问题。
给定两个有序的符号序列X=〈x1,x2,…,xm〉和Y=〈y1,y2,…,yn〉，求出X和Y的最长公共子序列。X的子序列就是去掉一些元素（可能是所有，也可能一个没有）后的X。例如，〈A,B,C,D,E,F,G〉的一个子序列是〈B,C,E,G〉。X和Y的最长公共子序列的长度度量了这两个序列的相似程序。例如，若两个序列是DNA链中的基对，则当它们具有长的公共子序列时我们认为它们是相似的。若X有m个符号且Y有n个符号，则X和Y分别有2m和2n个可能的子序列。
7除非m和n很小，否则选择X和Y的所有可能子序列做匹配将花费使人望而却步多的时间。第15章将介绍如何使用一种称为动态规划的一般技术来有效地求解这个问题。
给定一个依据部件库的机械设计，其中每个部件可能包含其他部件的实例，我们需要依次列出这些部件，以使每个部件出现在使用它的任何部件之前。若该设计由n个部件组成，则存在n!种可能的顺序，其中n!表示阶乘函数。因为阶乘函数甚至比指数函数增长还快，（除非我们只有几个部件，否则）先生成每种可能的顺序再验证按该顺序每个部件出现在使用它的部件之前，是不可行的。这个问题是拓扑排序的一个实例，第22章将介绍如何有效地求解这个问题。
给定平面上的n个点，我们希望寻找这些点的凸壳。凸壳就是包含这些点的最小的凸多边形。直观上，我们可以把每个点看成由从一块木板钉出的一颗钉子来表示。凸壳则由一根拉紧的环绕所有钉子的橡皮筋来表示。如果橡皮筋因绕过某颗钉子而转弯，那么这颗钉子就是凸壳的一个顶点（例子参见图33-6）。n个点的2n个子集中的任何一个都可能是凸壳的顶点集。仅知道哪些点是凸壳的顶点还很不够，因为我们还必须知道它们出现的顺序。所以为求凸壳的顶点，存在许多选择。第33章将给出两种用于求凸壳的好方法。
虽然这些问题的列表还远未穷尽（也许你已经再次从本书的重量推测到这一点），但是它们却展示了许多有趣的算法问题所共有的两个特征：
1.存在许多候选解，但绝大多数候选解都没有解决手头的问题。寻找一个真正的解或一个最好的解可能是一个很大的挑战。
2.存在实际应用。在上面所列的问题中，最短路径问题提供了最易懂的例子。一家运输公司（如公路运输或铁路运输公司）对如何在公路或铁路网中找出最短路径，有着经济方面的利益，因为采用的路径越短，其人力和燃料的开销就越低。互联网上的一个路由结点为了快速地发送一条消息可能需要寻找通过网络的最短路径。希望从纽约开车去波士顿的人可能想从一个恰当的网站寻找开车方向，或者开车时她可能使用其GPS。
8
算法解决的每个问题并不都有一个容易识别的候选解集。例如，假设给定一组表示信号样本的数值，我们想计算这些样本的离散傅里叶变换。离散傅里叶变换把时域转变为频域，产生一组数值系数，使得我们能够判定被采样信号中各种频率的强度。除了处于信号处理的中心之外，离散傅里叶变换还应用于数据压缩和大多项式与整数相乘。第30章为该问题给出了一个有效的算法——快速傅里叶变换（通常称为FFT），并且这章还概述了计算FFT的硬件电路的设计。
数据结构
本书也包含几种数据结构。数据结构是一种存储和组织数据的方式，旨在便于访问和修改。没有一种单一的数据结构对所有用途均有效，所以重要的是知道几种数据结构的优势和局限。
技术
虽然可以把本书当做一本有关算法的“菜谱”来使用，但是也许在某一天你会遇到一个问题，一时无法很快找到一个已有的算法来解决它（例如本书中的许多练习和思考题就是这样的情况）。本书将教你一些算法设计与分析的技术，以便你能自行设计算法、证明其正确性和理解其效率。不同的章介绍算法问题求解的不同方面。有些章处理特定的问题，例如，第9章的求中位数和顺序统计量，第23章的计算最小生成树，第26章的确定网络中的最大流。其他章介绍一些技术，例如第4章的分治策略，第15章的动态规划，第17章的摊还分析。
难题
本书大部分讨论有效算法。我们关于效率的一般量度是速度，即一个算法花多长时间产生结果。然而有一些问题，目前还不知道有效的解法。第34章研究这些问题的一个有趣的子集，其中的问题被称为NP完全的。
为什么NP完全问题有趣呢？第一，
9虽然迄今为止不曾找到对一个NP完全问题的有效算法，但是也没有人能证明NP完全问题确实不存在有效算法。换句话说，对于NP完全问题，是否存在有效算法是未知的。第二，NP完全问题集具有一个非凡的性质：如果任何一个NP完全问题存在有效算法，那么所有NP完全问题都存在有效算法。NP完全问题之间的这种关系使得有效解的缺乏更加诱人。第三，有几个NP完全问题类似于（但又不完全同于）一些有着已知有效算法的问题。计算机科学家迷恋于如何通过对问题陈述的一个小小的改变来很大地改变其已知最佳算法的效率。
你应该了解NP完全问题，因为有些NP完全问题会时不时地在实际应用中冒出来。如果要求你找出某一NP完全问题的有效算法，那么你可能花费许多时间在毫无结果的探寻中。如果你能证明这个问题是NP完全的，那么你可以把时间花在开发一个有效的算法，该算法给出一个好的解，但不一定是最好的可能解。
作为一个具体的例子，考虑一家具有一个中心仓库的投递公司。每天在中心仓库为每辆投递车装货并发送出去，以将货物投递到几个地址。每天结束时每辆货车必须最终回到仓库，以便准备好为第二天装货。为了减少成本，公司希望选择投递站的一个序，按此序产生每辆货车行驶的最短总距离。这个问题就是著名的“旅行商问题”，并且它是NP完全的。它没有已知的有效算法。然而，在某些假设条件下，我们知道一些有效算法，它们给出一个离最小可能解不太远的总距离。第35章将讨论这样的“近似算法”。
并行性
我们或许可以指望处理器时钟速度能以某个持续的比率增加多年。然而物理的限制对不断提高的时钟速度给出了一个基本的路障：因为功率密度随时钟速度超线性地增加，一旦时钟速度变得足够快，芯片将有熔化的危险。所以，为了每秒执行更多计算，芯片被设计成包含不止一个而是几个处理“核”。我们可以把这些多核计算机比拟为在单一芯片上的几台顺序计算机；换句话说，它们是一类“并行计算机”。为了从多核计算机获得最佳的性能，设计算法时必须考虑并行性。第27章给出了充分利用多核的“多线程”算法的一个模型。从理论的角度来看，该模型具有一些优点，它形成了几个成功的计算机程序的基础，包括一个国际象棋博弈程序。
10
练习
1.1-1 给出现实生活中需要排序的一个例子或者现实生活中需要计算凸壳的一个例子。
1.1-2 除速度外，在真实环境中还可能使用哪些其他有关效率的量度？
1.1-3 选择一种你以前已知的数据结构，并讨论其优势和局限。
1.1-4 前面给出的最短路径与旅行商问题有哪些相似之处？又有哪些不同？
1.1-5 提供一个现实生活的问题，其中只有最佳解才行。然后提供一个问题，其中近似最佳的一个解也足够好。
