第 1章引言

本章学习目标 
.掌握算法的定义 

.掌握算法效率的基本概念 

.了解求解问题可能存在效率不同的算法 


1.1算法的定义
算法的英文 Algorithm来自于一位叫 al-Khwˉarizmˉ.的波斯数学家。他在大约公元前 825年，写了一本叫 On the Calculation with Hindu Numerals的书，该书主要列举了加、减、乘、除和计算圆周率数值的计算方法。该书后被翻译成拉丁文 Algoritmi de numero Indorum，英文的 Algorithm就来自拉丁文 Algoritmi。
什么是算法？简单地说，算法就是按照一定步骤解决问题的办法。这个定义里面蕴含了算法的两个重要属性：一个属性是，算法一般包括一系列有限的步骤，这些步骤能快速完成；另一个属性是，算法要能正确地给出具体问题的解。
“民以食为天”，下面通过一个与我们日常生活息息相关的例子来说明算法的这两个属性。红烧肉是中国一道非常经典的家常菜肴，烹制红烧肉的过程就可以总结为一个算法。这个算法的输入是五花肉和各种调料，如葱、姜、蒜、酱油和糖等，输出当然就是可口诱人的红烧肉（如图 1.1）。根据输入，烹制这道菜肴的步骤包括： 
.五花肉洗净，切 4cm见方的块备用 

.葱切大段、姜切片、蒜剥好备用 

.用纱布将大料、花椒、桂皮包好封好口备用 

.锅中做少许油，凉油时下入白糖用铲子慢慢炒制 

.锅中的糖变成深红色时烹入酱油，下入切好的五花肉 

.不停地煸炒五花肉至糖色裹匀并微微出油 

.下入 60.C左右的温水至刚好没过肉 

.下料酒、放入香料包后大火做开 

.盖盖改小火慢慢炖五花肉至 9成熟 

.入盐和少许糖调味后继续焖五花肉至松软入味 

.捡去香料包，大火将汤汁收到红亮浓稠即可出锅食用


以上制作红烧肉的步骤就是一个算法。首先，以上步骤针对的是“如何烹制红烧肉”这一具体问题。其次，解决这个问题包括一系列特定的步骤，比如什么时候加水，什么时候加料酒等。根据这些步骤，大家都能做出色、香、味差别不大的红烧肉。
图 1.1烹制红烧肉示意图
当然，除了以上这两个重要的属性外，我们还可以发现烹制的步骤数是有限的，且整个烹制时间大约需要一小时左右。对于一道普通家庭常常烹制的菜肴而言，一小时是可以接受的。如果一道菜的烹制时间需要一天或者是一个月，那么它就很难成为流行的家常菜肴。也就是说，一个算法除了能解决问题，还要能在一个合理的时间内得到它的解。
此外，我们描述这个“烹制红烧肉”算法采用的是自然语言。也许读者会对此有些疑问，认为算法都是用计算机程序设计的语言，如大家熟悉的 C++、Java等来描述。其实，是否是算法和采用什么语言来描述并没有直接的关系。只要描述算法的语言能让读算法的人看懂，哪怕是自然语言也能定义一个算法。
以上例子告诉我们，算法并不神奇，我们日常的生活就会遇到各种算法。当然，算法还有其他更为严谨的定义，我们并不准备一一列举这些定义，下面将从算法的两个重要属性来进一步讨论它。 
1.1.1算法的属性
本书所讨论的是计算机领域内的算法，也就是说解决问题的类型是计算问题。这种情况下，算法是一个定义明确的计算过程，可以以一些值或一组值作为输入，产生一些值或一组值作为输出。因此，算法也可以说是将输入转为输出的一系列有限计算步骤。比如，前面红烧肉的例子中，输入就是五花肉和各种配料，输出当然是如图 1.1右图所示的红烧肉。
算法的第一个重要属性就是正确，也就是说能正确的求解问题。对于一个不能得到问题正确解的算法，不管这个算法设计得多么有技巧，具有何种奇思妙想，对给定的问题而言都没有意义。比如，现在的问题是烹制红烧肉，但是给出的算法却只能烹制出糖醋里脊，显然给出的这个算法对于烹制红烧肉这一问题而言没有意义。因此，设计某个问题的算法和分析该算法的前提，就是该算法要能求解出该问题的正确解。
在某些情况下，我们也能接受在一定概率下获得的正确解。比如我们常用的 RSA公钥加密算法中 ①，需要确定给定大数（如数百位长度）是否为素数。三位 MIT的教授设计了一个非常高效的算法来判断一个大数是否为素数，但是判断结果并不总是正确，即存在误判。也许读者会认为，既然 RSA算法并没有得到正确解，怎么它依然是加密算法中最重要的算法呢，甚至这三位发明人还因为这个算法获得了 2002年的图灵奖？这是因为，尽管存在误判，但这个误判出现的概率异常低 ——大约千万亿次才出现一次。因此，获得正确解也可以允许算法出错，只要这个出错的概率在我们可以控制的范围内就可以（见第 11章）。
此外，为了在合理时间得到有些问题的解，我们往往会放弃获得精确正确解的可能，而是尝试得到该问题的一个近似的正确解。近似算法求解的问题一般属于 NPC问题（ 12.3.4节），这些问题目前没有多项式时间算法可以求解它们的最优解，但通过近似算法可以在多项式时间求得一个次优解。
算法的另一个重要属性就是快速。快速意味着对于一个问题，可能存在用不同的算法都能得到正确的解，但其中有的算法速度更快。我们希望找到那个速度最快的算法。
追求更快的速度，是受人类本能的驱使，人类科学技术的一个驱动力就是追求速度的极致。这里的速度含义广泛，比如要做到真正的“朝辞白帝彩云间，千里江陵一日还”，我们现在有了汽车、火车、高速列车（图 1.2）和飞机等交通工具。杜甫的“烽火连三月，家书抵万金”，表达了快速和远方亲人取得联系的遐思。现在的微信、电话和各种视频通信软件，真正实现了人们快速通信的愿望。当然，算法还有许多其他的属性，比如简洁、通用和模块化等。本书重点关注的就是正确和快速这两个属性。
图 1.2高速列车 

1.1.2效率的定义
快速是衡量算法效率的一个重要属性。对于算法效率，除了包括算法的运行时间，也会包含算法执行过程中所占用的计算空间。在实际的分析过程中，往往假定算法效率是待处理问题输入规模 n的函数。还是以烹制红烧肉为例，当输入从 2.5千克五花肉增 
① RSA为该算法三位发明人姓氏首字母，他们分别是 Ron Rivest、Adi Shamir和 Leonard Adleman 
加到 25千克五花肉，显然所需要的烹制时间会增加。随着输入规模 n的增加，烹制时间 T可能增加 5倍、 10倍或是没变。这个增长趋势被称为算法的时间复杂度。
对于计算算法的时间复杂度，也许读者认为只需要取一系列不同规模的输入数据在机器上运行算法，得到各个输入数据的算法运行时间即可。比如，可以取输入规模 n分别等于 50、500、5000这三组数据，然后分别求出这三组输入数据对应的时间，就可以得到算法的时间复杂度。然而，这种直观的计算存在两点不足： 
.	这种计算将依赖于算法所运行机器的性能。运算算法的机器硬件配置可能不同，如 CPU、内存等，这导致得到的计算时间也不一样。比如说，对于某个问题，张某和李某两人各自提出了两个不同的算法。张某的算法在他的机器上耗时为 5s，而李某的算法在其机器上耗时为 100s。这时，我们并不能得出张某的算法效率要优于李某这一结论。因为，他们各自算法的运算时间是在不同的机器上得到的。这就好比他们测量时用的尺的刻度不一样。那读者会想，如果用同一台机器运算他们的算法，不就可以比较了吗？用同一台机器依然会造成算法分析的困难，如选用的程序语言，编程技巧等都会造成两个算法运行时间的差异，然而这种差异并不是由于算法本身的差异造成。因此，算法效率的度量不应该受算法所运行的机器、实现算法的程序语言和编程技巧等因素影响。 

.	以上计算方式并不能回答当输入规模 n没有落在其给定范围时的算法效率。比如，当 n = 1000时，算法运行时间可能是以分钟计，似乎这个效率可以接受。但是，当 n = 10000时，算法的运行时间也许就是按年计了。因此，通过采样输入规模并不能确定算法的时间效率，算法时间复杂度的函数应该连续。


为了克服以上困难，就需要引入算法的渐进分析法。当采用渐进分析时，往往假定输入规模 n趋向无穷大。将输入规模扩展到无穷大，再来量化算法效率这一想法，是算法分析最为重要的一个思想。这样做的好处是，不仅能得到一个算法运行时间的连续函数，而且其计算结果与算法运行的硬件配置无关、与实现算法的程序设计语言无关、与程序设计语言的编译环境无关（我们将在 2.3节详细介绍渐进分析法）。比如，一个算法执行时间为 35n + 102。当 n》 4时，35n相对于 102对算法时间有更大影响。随着 n逐渐增大， n就成为影响算法执行的主要因素。当 n趋向无穷大时， 35n + 102就可以写作 O(n)，意味着算法执行时间与输入规模呈线性关系。时间函数 35n + 102中的低次项 102和系数 35在算法时间复杂性度量时被去除，是因为它们可能是由机器配置、实现语言或者编译器版本等因素造成，而这些都不是影响算法执行时间的主要因素。
执行时间函数 35n + 102被记为 O(n)，其中的记号 O（读作大欧）表示算法执行时间的度量函数。比如一个算法的时间复杂度为 O(n)。这意味着，当输入规模 n = 100，其运行时间为 T；那么当输入规模增加到 n = 1000时，其运行时间则为 10 × T，这表示这个算法的时间复杂度随着输入规模呈线性变化。也就是说，当输入规模增加时，算法运行时间也会增加，但增加的量变化不大。再比如，另一个算法的时间复杂度为 O(2n)，则该算法时间复杂度随着输入规模呈指数变化。这意味着如果输入规模增加一点点，算法运行时间就会发生急剧的增加。
这里我们先给出一个简单的关于算法效率的度量。如果算法的时间复杂度随着输入规模 n呈多项式规模变化，那我们认为从效率来说，这是一个可以接受的算法。形如 O(log n)、O(n)、O(n log n) ①、O(n2)、O(n3)的都是多项式时间复杂度。若算法时间复杂度是 O(2n)、O(1.5n)、O(e2)等，则称它们是指数时间复杂度算法。对于指数时间复杂度算法，我们认为这是一个糟糕的算法（如图 1.3）。
图 1.3三个典型的时间复杂度函数 


1.2算法设计与分析举例
前节给出了算法的定义，也介绍了算法效率。那么对于一个具体的问题而言，真的可以通过设计从而得到一个相对高效的算法吗？下面将通过两个具体的例子来介绍的确存在设计技巧，可以得到更为快速的算法。 
1.2.1寻找局部高点 -1D
设想， 2046年，地球宇航员登陆了类地球行星 HD85512b。但是因为意外，登陆的宇宙飞船已经损毁，只剩下一辆运输车。宇航员需要找到一处水源地来补充给养，由于登陆的地点在该行星的一片山区，他必须坐着运输车在这片山区寻找水源地。假设该行星的水源一般都出现在山头。那么，他该如何快速找到水源地呢？
为了设计算法解决以上问题，我们首先需要将该问题转化成一个计算问题。也就是将问题形式化描述，尤其是需要量化问题的输入与输出。该问题可以看作是有 n个数据的输入序列 A[0], A[1], ··· , A[n . 1]，每一个数据 A[i]的索引 i对应于山区的一个采样点，数据的值就是该采样点的海拔。输出为局部高点的索引 i，该点须满足 A[i . 1]《 A[i]《A[i+1]。为了便于计算，我们假设序列以外的海拔为负无穷，即A[.1] = A[n]= .∞。
如图 1.4所示， A[2]和 A[5]都是满足条件的局部高点。注意题目要求返回的是一个局部高点，而不是最高点。此外，这个局部高点是整个输入序列中的任意一个。图 1.4中的输入序列，返回 i =2或者 i =5都是正确的解。 
1.简单的算法
由于存在边界条件 A[.1] = A[n]= .∞，因此任意输入序列至少存在一个局部高
①本书中除非特别说明，所有的对数均以 2为底。
图 1.4局部高点
点。比如，输入序列是一个连续递增序列，那么最后一个元素就是局部高点。读者可以自行证明这个结论。
求局部高点问题有一个简单直接的算法，就是从第一个元素开始，判断其是否满足局部高点的条件。如果满足则返回该数的索引，否则判断下一个元素。如此循环地判断输入序列的每一个元素直到找到一个局部高点为止。
该算法非常简单，那么怎么分析这个算法时间复杂度呢？粗略地看，似乎算法运行的快慢与局部高点在序列中的位置有关。因为，这个高点有可能在序列的第一个位置就出现，也有可能在最后一个位置出现。如果局部高点在第一个元素就出现，那么算法执行一次比较就能得到结果，这是最好情况下的执行效率。算法分析时基本不会将最好情况下的时间效率作为评价算法效率的标准。原因非常简单，我们并不能保证每一次处理的输入序列总能满足最好情况的条件，即第一个元素总是满足条件的局部高点。
如果局部高点在最后一个元素才出现，那么算法需要执行 n次计算才能得到结果，这是最坏情况下的执行效率。需要强调的是，在最坏情况下的算法时间复杂度，可以用来表征算法的效率 ①。因此，该算法的时间复杂度 T1(n)= O(n)。 

2.更好的算法
前一个算法直观，容易实现，但并不是最优的算法。现在考虑改进以上算法，改进的思路是减少查找次数。由于题目要求的是找到任意一个高点，这意味着并不一定需要扫描整个输入序列，而只需要尽快确定任意一个高点所在位置即可。为了提高查找的效率，首先需要确定从序列的哪个位置开始查找，然后再确定查找的范围。
究竟从序列的哪个位置开始查找呢？一个合理的选择就是从序列的中间位置开始查找。这是因为如果序列中存在一个高点，它要么是序列中间的这个元素，要么在中间元素左边部分的序列，要么在中间元素右边部分的序列。如果高点就在序列中间位置，那么就只需要一次查找。如果高点不在中间位置，只要能确定高点是在中间元素左边或右边部分的序列，就可以在执行一次查找后，缩小一半的搜索范围。也就是说，执行一次查找要么很幸运找到高点，要么可以缩小下一次搜索的范围。
当确定从中间元素开始查找后，下面需要考虑的就是一旦中间元素不是高点，那能否马上确定高点的搜索范围？可以根据中间元素与其相邻元素大小关系来确定高点的搜索范围。如图 1.5，假设中间元素索引为 i = n/2，比较中间元素与其相邻元素大小关系后存在以下三种情况： 
(1) A[i]满足局部高点的条件，即 A[i . 1]《 A[i]《 A[i + 1]，则返回 i（如图 1.5(a)）。
①本书以后在未作特别说明的情况下，均采用最坏情况下的时间复杂度度量算法效率。
图 1.5三种条件示意图 
(2)如果 
A[i] < A[i . 1]，在输入数组的左半部分一定存在一个局部高点，这是因为 A[i]往左边有上升趋势。因此，下一次需要搜索的序列就是 A[0], A[1], ··· , A[i . 1]（如图 1.5(b)）。 

(3)如果 A[i] < A[i + 1]，在输入数组的右半部分一定存在一个局部高点（原因同 

(2)
），下一次需要搜索的序列则是 A[i+1], A[i+2], ··· , A[n.1]（如图 1.5(c)）。


由于是找到一个高点，因此在做出一次比较后，就可以缩小一半的搜寻范围，只需在剩余的序列中寻找可能的高点。比如，初始情况下输入元素个数为 n，经过一次比较可以确定的是局部高点要么在输入序列的左半部分，要么在右半部分 ①。那么，下一次需要查找的元素大小就变成了 n/2。对这 n/2个元素，执行与以上相似的计算，即选择这 n/2个元素中的中间元素开始查找。经过第二次查找后，要么幸运地找到高点，要么可以将搜索范围缩小至 n/4（n/2的一半）。依此过程进行查找，直到找到输入序列的一个高点为止。
那么，该怎么分析以上算法的时间复杂度呢？如图 1.6所示的序列，不妨将该序列想象成长度为 n的蛋糕。经过第一次比较后，将长为 n的蛋糕一分为二，长度变为 n/2。经过第二次比较，长度为 n/2的蛋糕变成长度为 n/4。由于序列一定存在一个高点，所
图 1.6算法分析示意
①不考虑最好情况，即经过一次比较马上就得到解的情况。
以最坏情况下不妨设需要切分 k次，此时剩下最后一个元素，该元素必是序列中的一个高点。那么，可以得到 n/2k =1，等式两边取以 2为底的对数，得 k = log n。因此，该算法最坏情况下需要运行的次数为 log n，也就是说改进后算法的时间复杂度为 T2(n)= O(log n)。
如果 n = 1000，这两个算法的运行时间没有显著区别（机器配置为 CPU:i7，内存:8G），大约都是 0.1ms。但是，当 n = 1000000时，前一个算法大约需要运行 13s，而改进后的算法所需时间大约为 0.001s。也就是说，新的算法在输入规模较大时，其效率相比较于第一个简单算法有显著提高。 
1.2.2图书管理
一个现代化的图书馆，不仅需要馆藏丰富，还需要能为读者提供快速查找图书的服务。不妨假设图书馆共能摆放 1万本图书，也就是有 1万个书位供使用。那么，随着这家图书馆不断的进书，管理员该如何来摆放图书，从而可以为读者提供快速查找图书的服务呢？ 
1.按到序摆放
一个简单的摆放原则就是按照书进入图书馆的顺序，依次摆放在书架上。如图 1.7所示，当前购买的是《昆虫学》这本书，书架的空位是 1010，就将《昆虫学》放在 1010位。下次再进一本新书，就将它放在 1011。如果一个读者借走了其中《概率》这本书，那么管理员就将《概率》这本书之后的所有书向左推一位。也就是说，书与书之间不留空位。这样不管是新书进馆，还是读者还回《概率》这本书，都只需要将它放在现有书的最后即可。
图 1.7按到序摆放
按照以上规则管理书籍，对管理员而言书架上的书井井有条。然而，如果一位读者想借《昆虫学》这本书，管理员就必须从书架的第一个书位开始寻找，依次比对书架上每一本书名，直到找到《昆虫学》这本书为止。显然，按照以上方式管理图书，对于一个大型图书馆而言尽管进书时书的摆放简单清楚，但对于找书这项工作而言就显得费时费力。如果有 n个书位，那么按序摆放组织图书，检索图书的耗时就是 O(n)，即检索的时间随着书位的多少呈线性时间规模变化。 

2.按哈希表摆放
为了解决找书费时的问题，管理员在进得一本新书后，可先将该书的书名 title输入一个哈希函数 hash(title)，这个哈希函数 hash运算后的输出结果为书位的索引。比如，书名 title=《昆虫学》，那么 hash(《昆虫学》 )=1011。也就是说，《昆虫学》这本书应该放在编号为 1011的书位。此时，各个书位就称为哈希表，如图 1.8所示。
图 1.8按哈希表摆放
按照以上方式摆放书的好处是可以实现快速搜索。当读者提出想借《昆虫学》这本书时，管理员只需要将书名《昆虫学》输入至哈希函数，得到 1011返回结果，管理员就可以立即去书位 1011取得该书。显然，按照哈希表方式组织图书可以显著提高检索书位的效率。此时，检索的时间效率与书位的多少没有关系，只与哈希函数的运算时间有关。哈希函数的一次计算时间往往为常数，因此按照哈希表方式组织图书，其搜索的执行时间为 O(1)。
O(1)为常数的执行时间，这个时间可以是几秒或几分钟，表示算法执行时间不随处理数据的大小变化。比如说，处理规模为 10个数据的时间是 20s，那么处理百万数据规模的时间依然是 20s。
那么哈希函数到底采用什么函数呢？显然，该函数需要能将诸如书名这样的字符转换为存储位置的索引。这一点对计算机而言非常简单，因为计算机内存储的数据对象其本质都是数字。比如，“昆虫学”这个书名字符串，其计算机内存储的编码就是“\u6606\u866b\u5b66”。那么，这数字串该如何变成存储位置的索引呢？这需要先确定存储位置的大小。由于存储空间总是有限的，我们也不能预先确定到底有多少数据存储。因此，一个合理的方法是先确定一个中等规模的哈希表空间 n。由于书名转换为数字 m后，其大小可能超出 n的范围。这时哈希函数就需要将较大的数 m转化为一个较小的数，以便与数字 m对应的书名能在大小为 n的哈希表中确定其存储位置。最简单的哈希函数就是取余 ——mod运算，比如， mod(m = 1000,n = 13) = 12。通过取余，可以将一个大数 m = 1000，转换为一个较小的数 12。
哈希表 (也称为字典表 )这个数据结构就是通过哈希函数计算其存储位置的数组。可以将哈希表看作一个数据对。其中，一个数据称为 key，另一个数据称为 value。书名可以作为 key，value可以是作者名、出版社、出版年份的集合。比如， {“算法设计与分析”：[“程振波” ,“清华大学出版社” ,“2017”]}，这个哈希表的 key就是“算法设计与分析”，value则等于字符序列 [“程振波” ,“清华大学出版社” ,“2017”]。
按照哈希表存储的数据，可以通过 key来索引。比如申明一个称为 book的哈希表，其中有两条数据， book = {“算法设计与分析”： [“程振波” ,“清华大学出版社” ,“2017”];“机器学习” :[“周志华” ,“清华大学出版社” ,“2016”]}。那么通过书名就可以索引到作者名、出版社和出版年份这些数据，即 book[“算法设计与分析” ]=[“程振波” ,“清华大学出版社” ,“2017”]，book[“机器学习” ]=[“周志华” ,“清华大学出版社” ,“2016”]。需要特别强调的是，哈希表中的 key对应的数据不能有重复。比如， book中只能有一条数据的 key为“算法设计与分析”。 


1.3小结
算法可以简单地看作是解决问题的办法。面对或简单或复杂的各种问题，解决问题的办法可以是“条条大路通罗马”。哪怕是针对相同的一个问题，求解该问题的算法往往也各不相同，其运算的时间也会有很大的差异。而为了得到高效的算法，不仅可以通过与寻找局部高点类似的改变计算过程得到，也可以通过如图书管理中介绍的改变数据组织模式得到。
在确保算法正确的前提下，如何筛选出一个高效的算法呢，为此，就需要通过渐进分析法量化算法的时间复杂度，从而为不同算法之间的取舍建立一个一致的标准。算法不是万能的，并不是所有的问题都能给出一个解。但是，解决问题的办法依然有迹可循。