书名：趣学算法（第2版）
ISBN：978-7-115-59600-0
本书由人民邮电出版社发行数字版。版权所有，侵权必究。
您购买的人民邮电出版社电子书仅供您个人使用，未经授权，不得以任何方式复制和传播本书内容。
我们愿意相信读者具有这样的良知和觉悟，与我们共同保护知识产权。
如果购买者有侵权行为，我们可能对该用户实施包括但不限于关闭该帐号等维权措施，并可能追究法律责任。
著 陈小玉
责任编辑 张 涛
人民邮电出版社出版发行 北京市丰台区成寿寺路11号
邮编 100164 电子邮件 315@ptpress.com.cn
网址 http://www.ptpress.com.cn
读者服务热线：(010)81055410
反盗版热线：(010)81055315
读者服务：
微信扫码关注【异步社区】微信公众号，回复“e59609”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
本书是用轻松有趣的方法学习算法的入门指南。按照算法策略分为8章。第1章以算法之美、趣味故事引入算法，讲解算法复杂度的计算方法，以及爆炸性增量问题。2～7章讲解经典算法，包括贪心算法、分治算法、动态规划算法、回溯法、分支限界法、网络流算法。第8章讲解实际应用中的算法和高频面试算法，包括启发式搜索、敏感词过滤、LRU算法、快慢指针、单调栈、单调队列、零钱兑换、股票交易等。每一种经典算法都有4～8个实例，多数按照问题分析、算法设计、完美图解、算法详解、算法分析及优化拓展的流程进行讲解。全书讲解清晰，通俗易懂，紧扣工程教育认证的要求和实用性，力求满足新工科人才培养的需要。
本书为河南省“十四五”普通高等教育规划教材，提供了丰富的教学资源与答疑服务，包括源代码、课件、教案、习题、在线答疑和在线测试系统。本书既适合作为高等院校计算机及相关专业的算法教材，也适合对算法感兴趣的初学者以及需要提升技术能力的在职人员阅读。
本书是作者多年教学经验积累的成果，自2017年出版以来，重印23次，受到广大读者的欢迎；同时，被多所高校作为教材使用，得到广大师生的一致好评。2018年，本书获得“河南省教育科学研究优秀成果”二等奖，繁体版已授权给中国台湾碁峰出版社出版。
本书实例丰富、通俗易懂，以大量图解展示算法的求解过程，重点讲解遇到实际问题如何分析和设计算法，讲解方式富有启发性，有利于激发学生的学习兴趣和创新潜能。书中汇集了作者根据多年教学实践总结出的各种算法的解题技巧并对知识进行了优化拓展。读者阅读时既能掌握解题的方法，又拓宽了视野，有利于培养其逻辑思维能力，为解决复杂性工程问题奠定了基础。本书与大多数算法教材讲述严肃和只提供伪代码不同，不仅增加了很多有趣的项目实例，而且提供配套的课件、在线答疑、在线测试和可运行的源代码。
本书第1版出版后，在收到大量好评的同时，也收获了一些宝贵的修订、改进意见。例如，教师普遍反映教学效果良好，学生非常喜欢、容易理解，但是教材过厚；计算机技术日新月异，教材需要不停地增加新技术，淘汰旧技术，才能紧跟时代，激发学生的学习兴趣；及时融入相关学科领域的最新科研理念不仅能达到工程教育认证的要求，而且能达到国家培养新工科人才的要求。综合以上因素，笔者认为很有必要结合多年教学实践和教学改革创新成果对本书第1版进行修订。
本书的修订坚持以下几个方面，增加新算法和优化算法，融入学科领域科研新发展技术；增加跨学科、多学科融合的项目实例，适应新工科人才培养的需要；增加不同类别算法实例，拓宽算法学习思维，启发创新潜能；增加实际工程应用中的算法和面试算法，提高学生学习兴趣；删减同类别算法实例和部分源代码，以突出重点、详略得当。
（1）动态规划算法，增加爬楼梯、最长上升子序列、0/1背包优化、完全背包、树形动态规划。
（2）回溯法，增加深度优先搜索、回溯法模板（子集树、m叉树、排列树）。
（3）分支限界法，增加广度优先搜索。
（4）网络流算法，增加Dinic算法及当前弧优化。
（5）启发式搜索在游戏中的应用，包括A*算法、IDA*算法、八数码游戏。
（6）多模匹配算法在敏感词过滤中的应用，包括字典树、AC自动机、敏感词过滤。
（7）LRU缓存淘汰算法的应用场景，包括LRU缓存机制、哈希链表、LRU算法实现。
（8）高频面试算法，包括快慢指针、单调栈、单调队列、零钱兑换、股票交易。
（1）马克思手稿中的数学题。
（2）大整数除法。
（3）最优三角剖分、石子合并、最优二叉搜索树。
（4）线性规划、单纯形算法、圆桌问题、方格取数问题。
（5）实战源代码（仅保留关键代码）。
以上删除的所有内容仍可在网上阅读，其全部实战源代码都提供网络下载。
本书为河南省“十四五”普通高等教育规划教材，提供了丰富的教学资源与答疑服务，包括所有实例程序的源代码、课件、教学大纲、教案、习题、在线答疑和在线测试。
QQ群（514626235）会对读者提出的问题进行技术支持，并提供配书资源下载。
编辑联系邮箱：zhangtao@ptpress.com.cn。
您还可以扫码右侧二维码， 关注【异步社区】微信公众号，回复“e59600”直接获取,同时可以获得异步社区15天VIP会员卡，近千本电子书免费畅读。
有一天，一个学生给我留言：“我看到一些资料介绍机器人具有‘情感’，真是不可思议，我对这个特别感兴趣，但我该怎么做呢？”我告诉他：“先看算法书。”过了一段时间，这个学生苦恼地说：“算法书上那些公式和大段的程序不能执行，太令人抓狂！理论我好像懂了一点儿，却又用不上！”我向他推荐了一本内容简单一点儿的算法书，他仍然表示看不太懂。
问题出在哪里？数据结构？C语言？还是算法太枯燥、晦涩难懂？
这些问题的出现一点儿也不让人感到意外，你不会想到，有学生拿着C语言书问我：“这么多英文单词怎么办？for、if这样的单词是不是要记住？”我的天！我从来没考虑过把for、if这些当作英文单词，而且是要记的单词！这就像我们拿起筷子吃饭，端起杯子喝水，从来不会考虑自己喝的是H2O。这件事情彻底颠覆了我以前的教学理念，我终于理解为什么看似简单的问题，那么多人就是看不懂。他们真正需要的是一本简洁易懂的算法入门书。
有个学生告诉我：“大多数算法书上的代码都不能运行，或者运行时有各种错误，每每如此都感到迷茫，甚至崩溃……”我说：“你要理解算法而不是运行代码。”可这个学生告诉我：“你知道吗，我运行代码成功后是多么喜悦和自信！那种收获已经远远超越运行代码本身。”好吧，相信这本书将会给你满满的喜悦和自信。
本书从算法之美娓娓道来，既没有高深的原理，也没有枯燥的公式，是通过趣味故事引出算法问题，并结合大量的实例及绘图分析算法本质，而且给出代码实现的详细过程和运行结果。如果你读这本书的感觉像躺在躺椅上悠闲地读《普罗旺斯的一年》，那就对了！这就是我写这本书的初衷。
本书既适合那些对算法有强烈兴趣的初学者，也适合觉得算法晦涩难懂、无所适从的人，还适合作为高等院校计算机及相关专业的算法教材。读者阅读本书，不仅能够理解经典的算法设计，而且能获得足够多的实用技巧，以便更好地分析和解决问题，为学习更高深的算法奠定基础。
更重要的是——体会算法之美！
知识在于积累，学习需要耐力。学习就像挖金矿，或许你一开始毫无头绪，但转个角度、换个工具，时间久了总会找到门径。成功就是你比别人多走了一段路，甚至恰恰只是那么一小步。
第1个建议：多角度，对比学习。
学习算法时，可以先阅读一本简单的入门书，再综合几本书横向、多角度去看。例如学习动态规划，拿几本算法书，把涉及动态规划的章节都找出来，多角度对比分析，一些原理你会恍然大悟。
第2个建议：大视野，不求甚解。
经常有学生为了一个公式或几行代码“抛锚”，甚至停滞数日，沉浸在无尽的挫败感中，把自己弄得垂头丧气。其实你不必投入大量精力试图推导书上的每一个公式，或探究语法或技术上的细节。学算法就是学算法本身，首先是掌握算法思想、解题思路，然后是弄懂算法实现。算法思想的背后可能有高深的数学模型、复杂的公式推导，你理解了当然更好，不懂也没关系。算法实现可以用任何编程语言，所以不必纠结于C、C++、Java、Python……更不必考虑严格的语法规则，除非你要上机调试。所以建议还是先领会算法，写伪代码，在大脑中调试吧！
第3个建议：多交流，见贤思齐。
与同学、朋友、老师或其他编程爱好者一起学习和讨论问题，既是取得进步最为有效的办法之一，也是分享知识和快乐的途径。加入论坛、交流群，了解其他人在做什么、怎么做。遇到问题请教高手，可以感受到豁然开朗的喜悦。此外，论坛和群还会分享大量的学习资料和视频、举行不定期的培训讲座和读书交流会。记住，你不是一个人在战斗！
第4个建议：勤实践，越挫越勇。
实践是检验真理的唯一标准。古人云：“不积跬步，无以至千里。”请不要急切期盼大规模的成功商业案例，而看不起小的实践。大规模的成功商业案例不是我们目前要实践的内容。看清楚并走好脚下的每一步，比仰望天空更实际。多做一些实战练习，更好地体会算法的本质，在错误中不断成长，越挫越勇，相信你终究会有建树。
第5个建议：看电影，洞察未来。
不管是讲人工智能，还是讲算法分析，我都会建议学生们去看一看科幻电影，如《人工智能》《记忆裂痕》《绝密飞行》《未来战士》《她》等。奇妙的是，这些科幻的东西正在一步步地被实现，靠的是什么？人工智能。计算机的终极目标是实现人工智能，人工智能的核心是算法。未来的竞争是科技竞争，先进的科技需要人工智能。
“一心两本”学习法：一颗好奇心，两个记录本。
怀着一颗好奇心去学习，才能不断地解决问题，获得满足感，体会算法的美。很多科学大家的秘诀就是永远保持一颗好奇心。一个记录本用来记录学习中的重点、难点和随时突发的奇想；另一个记录本用来写日记或周记，记录一天或一周学了什么，有什么经验教训，需要注意什么，计划明天或下一周做什么。不停地总结和反思过去，计划未来，这样每天都有事做，心中就会有满满的正能量。
记住没有人能一蹴而就，付出才有回报。
（1）实例丰富，通俗易懂。用有趣的故事引入算法，从简单到复杂，让读者从实例中体会算法的设计思想。实例讲解通俗易懂，让读者获得最大程度的启发，锻炼分析问题和解决问题的能力。
（2）完美图解，简单有趣。结合大量完美绘图，对算法进行分解剖析，使复杂难懂的问题变得简单有趣，给读者带来巨大的阅读乐趣，使读者在阅读中不知不觉地学到算法知识，体会算法的本质。
（3）深入浅出，透析本质。用关键代码描述算法，既简洁易懂，又能抓住本质；算法思想描述及注释使代码更加通俗易懂。对算法设计初衷和算法复杂性的分析全面细致，既有逐步得出结论的推导过程，又有直观的绘图展示。
（4）实战演练，循序渐进。将每一个算法讲解清楚后，进行实战演练，使读者在实战中体会算法，增强自信，从而提高读者独立思考和动手实践的能力。丰富的练习题和思考题用于及时检验读者对所学知识的掌握情况，为读者从小问题出发到逐步解决大的复杂性问题奠定基础。
（5）算法解析，优化拓展。首先，对每一个实例都进行详细的算法解析，分析算法的时间复杂度和空间复杂度，随后对其优化拓展，以及提出算法改进的方法并进行算法详解和实战演练，最后与优化算法的复杂度进行对比，使读者在学习算法的高度上再上一个台阶，对算法优化有更清晰的认识。
（6）网络资源，技术支持。在线网站提供本书所有实例程序的源代码、练习题，以及答案解析。这些源代码可以自行修改和编译，以符合读者的需要。本书不仅提供源代码执行、调试说明书，还会对读者提出的问题进行技术支持。
写书是一项极其琐碎、繁重的工作，尽管我已经竭力使本书和网络支持接近完美，但仍然可能存在漏洞和瑕疵。欢迎读者提供反馈意见，这有利于我改进和提高，以帮助更多的读者。如果你对本书有任何建议，或者遇到问题需要帮助，既可以加入趣学算法交流QQ群（514626235）进行交流，也可以通过邮件联系本人（邮箱：rainchxy@126.com），我将不胜感激。
感谢我的家人和良师益友在本书编写过程中提供的大力支持！感谢提供宝贵意见的同事们！感谢提供技术支持的同学们！
1.1 打开算法之门
1.2 妙不可言——算法复杂性
1.3 一棋盘的麦子
1.4 神奇的兔子数列
1.5 算法学习瓶颈
1.6 本章小结
如果说数学是皇冠上的一颗明珠，那么算法就是这颗明珠上的光芒，算法让这颗明珠更加熠熠生辉，为科技进步和社会发展照亮了前进的路。数学是美学，算法是艺术。走进算法的人，才能体会它的无穷魅力。
多年来，我有一个梦想，希望每一位提到算法的人，不再立即紧皱眉头，脑海里闪现枯燥的公式、冗长的代码；我希望每一位阅读和使用算法的人，体会到算法之美，就像躺在法国普罗旺斯小镇的长椅上，呷一口红酒，闭上眼睛，体会舌尖上的美味，感受鼻腔中满溢的薰衣草的芳香……
瑞士著名的科学家Niklaus Wirth教授曾提出：数据结构+算法=程序。
数据结构是程序的骨架，算法是程序的灵魂。
在生活中，算法无处不在。每天早上起来，刷牙、洗脸、吃早餐，都在算着时间，以免上班或上课迟到；去超市购物，在资金有限的情况下，考虑先买什么、后买什么，算算是否超额；在家中做饭，用什么食材、调料，具体的烹饪方法和步骤如何，做完了还要品尝一下咸淡，看看是否做熟。所以，不要说你不懂算法，其实你每天都在用！
但是对于计算机专业算法，很多人都有困惑：我能看懂，但不会用！就像参观莫高窟里的壁画，看到它、感受它，却无法走进。每一个初学者都需要一把打开算法之门的钥匙，就如陶渊明《桃花源记》中说的“初极狭，才通人。复行数十步，豁然开朗。”
首先看一道某跨国公司的招聘试题。
写一个算法，求以下序列之和：
−1, 1, −1, 1, …, (−1)n
当你看到这个题目时，你会怎么想？for语句？while循环？
先看算法1-1：
//算法1-1
int sum1(int n){
int sum=0;
for(int i=1;i<=n;i++)
sum+=pow(-1,i);//表示（-1）^i
return sum;
}这段代码可以实现求和运算，但是为什么不这样算?！
再看算法1-2：
int sum2(int n){
int sum=0;
if(n%2==0)
sum=0;
else
sum=-1;
return sum;
}看到这段代码后你可能恍然大悟，原来可以这样啊？这不就是数学家高斯使用的算法吗？
一共50对数，每对数的和均为101，因此总和为：
(1+100)×50=5050
1787年，10岁的高斯用了很短的时间就算出了结果，而其他孩子却要算很长时间。
可以看出，算法1-1需要运行n+1次，如果n = 100 00，就要运行100 01次，而算法1-2仅仅需要运行1次！是不是有很大差别？
高斯的方法我也知道，但遇到类似的题还是……我用的笨办法也是算法吗？
答：是算法。
算法是对特定问题求解步骤的一种描述。
算法只是对问题求解方法的一种描述，它不依赖于任何一种语言，既可以用自然语言、程序设计语言（C、C++、Java、Python等）描述，也可以用流程图、框图来表示。通常情况下，为了更清楚地说明算法的本质，我们会去除计算机语言的语法规则和细节，采用“伪代码”来描述算法。“伪代码”介于自然语言和程序设计语言之间，它更符合人们的表达方式，容易理解，但它不是严格的程序设计语言。如果要上机调试，则需要转换成标准的计算机程序设计语言才能运行。
算法具有以下特性。
（1）有穷性：算法是由若干条指令组成的有穷序列，总是在执行若干次后结束，不可能永不停止。
（2）确定性：每条语句都有确定的含义，无歧义。
（3）可行性：算法在当前环境条件下可以通过有限次运算来实现。
（4）输入/输出：有零个或多个输入以及一个或多个输出。
算法1-2的确算得挺快的，但怎么知道我写的算法好不好呢？
“好”算法的标准如下。
（1）正确性：正确性是指算法能够满足具体问题的需求，程序运行正常，无语法错误，能够通过典型的软件测试，达到预期。
（2）易读性：算法遵循标识符命名规则，简洁易懂，注释语句恰当适量，方便自己和他人阅读，便于后期调试和修改。
（3）健壮性：算法对非法数据及操作有较好的反应和处理。例如，在学生信息管理系统中登记学生年龄时，若将21岁误输入为210岁，则系统应该有错误提示。
（4）高效性：高效性是指算法运行效率高，即算法运行所消耗的时间短。
（5）低存储性：低存储性是指算法所需的存储空间小。对于像手机、平板电脑这样的嵌入式设备，算法如果占用空间过大，则无法运行。算法占用的空间大小被称为空间复杂度。
除了（1）～（3）中的基本标准之外，好算法的评判标准是高效率、低存储。
（1）～（3）中的标准都好办，但时间复杂度怎么算呢？
时间复杂度：算法运行需要的时间。
算法的时间复杂度就是算法运行所需的时间。现代计算机一秒能计算数十亿次，所以不能用秒来具体计算算法消耗的时间。由于相同配置的计算机进行一次基本运算的时间是一定的，可以用算法基本运算的执行次数来衡量算法的效率，因此我们将算法基本运算的执行次数作为时间复杂度的衡量标准。
观察算法1-3并分析算法的时间复杂度。
//算法1-3
int sum=0; //运行1次
int total=0; //运行1次
for(int i=1;i<=n;i++){ //运行n+1次，最后一次判断不满足循环条件
sum=sum+i; //运行n次
for(j=1;j<=n;j++) //运行n×(n+1)次
total=total+i*j; //运行n×n次
}把算法1-3中所有语句的运行次数加起来：1+1+n+1+n+n×(n+1)+n×n。这可以用一个函数T(n)来表达：
T(n)=2n2+3n+3
当n足够大时，例如n=105，T(n)=2×1010+3×105+3。可以看出，算法的运行时间主要取决于最高项，小项和常数可以忽略不计。
用极限可以表示为
，C为不等于0的常数
T(n)和Cf (n)的函数曲线如图1-1所示。从图1-1可以看出，当n≥n0时，T(n)≤Cf (n)；当n足够大时，T(n)和f (n)近似相等。因此，我们用О(f (n))表示时间复杂度渐近上界，可以用这种表示法衡量算法的时间复杂度。算法1-3的时间复杂度渐近上界为О(f (n))＝О(n2)，用极限可以表示为
图1-1 时间复杂度渐近上界
渐近下界符号Ω(T(n)≥Cf (n))，如图1-2所示。从图1-2可以看出，当n≥n0时，T(n)≥Cf (n)；当n足够大时，T(n)和f (n)近似相等。因此，我们用Ω(f (n))来表示时间复杂度渐近下界。
图1-2 时间复杂度渐近下界
渐近精确界符号Θ(C1f (n)≤T(n)≤C2f (n))，如图1-3所示。从图1-3可以看出，当n≥n0时，C1f (n)≤T(n)≤C2f (n)；当n足够大时，T(n)和f (n)近似相等。这种两边逼近的方式更加精确近似，因此我们用Θ(f (n))来表示时间复杂度渐近精确界。
图1-3 渐进时间复杂度精确界
在实际应用中，通常使用时间复杂度渐近上界 О(f (n))来表示时间复杂度。
观察算法1-4并分析算法的时间复杂度。
//算法1-4
i=1; //运行1次
while(i<=n){ //可假设运行x次
i=i*2; //可假设运行x次
}对于算法1-4，我们无法立即确定while 以及i=i*2语句运行了多少次。这时可假设运行了x次，每次运行后i的值为2、22、23、…、2x，当i=n时结束，也就是当2x=n时结束，此时x=log2n，因此算法1-4的运行次数为1+2log2n，时间复杂度渐近上界为О(f (n)) = О(log2n)。
在算法分析中，渐近复杂度是对算法运行次数的粗略估计，大致反映问题规模增长趋势，而不必精确计算算法的运行时间。在计算渐近时间复杂度时，可以只考虑对算法运行时间贡献大的语句，而忽略那些运行次数少的语句。循环语句中处在循环内层的语句往往运行次数最多，它们是对运行时间贡献最大的语句。例如，在算法1-3中，total=total+i*j是对算法贡献最大的语句，只计算该语句的运行次数即可。
注意：不是所有算法都能直接计算运行次数。
例如算法1-5，在数组a[n]中顺序查找x并返回其下标i。如果没有找到，则返回−1。
//算法1-5
int findx(int x){ //在a[n]数组中顺序查找x
for(int i=0;i<n;i++){
if(a[i]==x)
return i; //查找成功，返回其下标i
}
return -1; //查找失败，返回-1
}对于算法1-5中的程序，我们很难计算到底执行了多少次，因为运行次数依赖于x在数组中的位置。如果第一个元素就是x，则执行1次（最好情况）；如果最后一个元素是x，则执行n次（最坏情况）；如果分布概率均等，则平均运行次数为(n+1)/2。
有些算法，如排序、查找、插入算法等，可以分为最好、最坏和平均情况分别求算法渐近复杂度。但考查一个算法时通常考查最坏的情况，而不是考查最好的情况，最坏情况对衡量算法的好坏具有实际意义。
空间复杂度：算法占用的空间大小。
空间复杂度的本意是指算法在运行过程中占用了多少存储空间。算法占用的存储空间包括：
（1）输入/输出数据；
（2）算法本身；
（3）额外需要的辅助空间。
输入/输出数据占用的空间是必需的，算法本身占用的空间可以通过精简算法来缩减，但缩减的量是很小的，可以忽略不计。算法在运行时所使用的辅助变量占用的空间（即辅助空间）才是衡量算法空间复杂度的关键因素。
请分析算法1-6的空间复杂度。
//算法1-6
void swap(int x,int y){ //交换x与y
int temp;
temp=x; //temp为辅助空间 ①
x=y; //②
y=temp; //③
}两数的交换过程如图1-4所示。
图1-4 两数的交换过程
图1-4中的步骤标号与算法1-6中的语句标号一一对应。算法1-6使用了辅助空间temp，空间复杂度为О(1)。
注意：在递归算法中，每一次递推都需要一个栈空间来保存调用记录，因此在分析算法的空间复杂度时，需要计算递归栈的辅助空间。
算法1-7用于计算n的阶乘，请分析其空间复杂度。
//算法1-7
int fac(int n){ //计算n的阶乘
if(n==0||n==1)
return 1;
else
return n*fac(n-1);
}阶乘是典型的递归调用问题，递归包括递推和回归。递推是将原问题不断分解成子问题，直至满足结束条件，返回最近子问题的解；然后逆向逐一回归，最终到达递推开始的原问题，返回原问题的解。
思考：试求5的阶乘，程序将怎样计算呢？
5的阶乘的递推和回归过程如图1-5和图1-6所示。
图1-5 5的阶乘的递推过程
图1-6 5的阶乘的回归过程
图1-5和图1-6所示的递推、回归过程是从逻辑思维上推理，以图的方式形象地表达出来的，但计算机内部是怎样处理的呢？计算机使用一种称为“栈”的数据结构，“栈”类似于一个放盘子的容器，每次从顶端放进去一个，拿出来的时候只能从顶端拿一个，不允许从中间插入或抽取，因此称为“后进先出”（last in first out）。
5的阶乘进栈过程如图1-7所示，5的阶乘出栈过程如图1-8所示。
图1-7 5的阶乘进栈过程
从图1-7和图1-8所示的进栈、出栈过程中可以很清晰地看到，子问题先被一步步地压进栈，直至直接可解得到返回值，再一步步地出栈，最终得到递归结果。在运算过程中，由于使用了n个栈空间作为辅助空间，因此阶乘递归算法的空间复杂度为О(n)。在算法1-7中，时间复杂度也为О(n)，因为n的阶乘仅比n−1的阶乘多了一次乘法运算（fac(n)=n*fac(n−1)）。如果用T(n)表示fac(n)的时间复杂度，则可以表示为
T(n)= T(n−1)+1
= T(n−2)+1+1
…
= T(1)+…+1+1
=n
图1-8 5的阶乘出栈过程
有一个古老的传说，一位国王的女儿不幸落水，水中有很多鳄鱼，国王情急之下下令：“谁能把公主救上来，就把女儿嫁给他。”很多人纷纷退让，一个勇敢的小伙子挺身而出，冒着生命危险把公主救了上来，国王一看是个穷小子，想要反悔，说：“除了女儿，你要什么都可以。”小伙子说：“好吧，我只要一棋盘的麦子。您在第1个格子里放1粒麦子，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，以此类推，每一个格子里麦子的粒数都是前一格子里麦子粒数的两倍。把这64个格子放满了就行，我就要这么多。”国王听后哈哈大笑，觉得小伙子的要求很容易满足，满口答应。结果发现，把全国的麦子都拿来，也填不完这64个格子……国王无奈，只好把女儿嫁给了这个小伙子。
棋盘上的64个格子究竟需要放多少粒麦子？
把每一个格子里需要放的麦子粒数加起来，总和为S，则：
S=1+21+22+23+…+263 ①
对式①等号的两边乘以2，等式仍然成立：
2S=21+22+23+…+263+264 ②
用式 ②减去式①，得：
S=264−1 ＝18 446 744 073 709 551 615
据专家统计，每颗麦粒的平均重量约41.9毫克，这些麦粒的总重量为：
18 446 744 073 709 551 615 × 41.9＝772 918 576 688 430 212 668.5（毫克）
≈7729 000（亿千克）
全世界人口按77亿计算，每人差不多可以分得100 000千克（即100吨）！
我们称这样的函数为爆炸增量函数。想一想，如果算法的时间复杂度是О(2n)会怎样？随着n的增长，算法会不会“爆掉”？我们经常见到有些算法调试没问题，运行一段时间也没问题，但在关键的时候宕机（shutdown）。例如在线考试系统，50人考试没问题，100人考试也没问题，但如果全校10 000人考试就可能宕机。
注意：宕机就是死机，指计算机无法正常工作，包括一切原因导致的死机。计算机主机出现意外故障而死机，一些服务器（如数据库服务器）死锁，服务器的某些服务停止运行等，都可以称为宕机。
常见的算法时间复杂度有以下几类。
（1）常数阶。
常数阶算法的运行次数是一个常数，如5、20、100。常数阶算法的时间复杂度通常用О(1)表示。
（2）多项式阶。
很多算法的时间复杂度是多项式，通常用О(n)、О(n2)、О(n3)等表示。
（3）指数阶。
指数阶算法的运行效率极差，程序员往往像躲“恶魔”一样避开这种算法。指数阶算法的时间复杂度通常用О(2n)、О(n!)、О(nn)等表示。
（4）对数阶。
对数阶算法的运行效率较高，通常用О(logn)、О(nlogn)等表示。
指数阶增量随着x的增加而急剧增加，而对数阶增长缓慢。它们之间的关系如下：
О(1)< О(logn)< О(n)< О(nlogn) < О(n2)< О(n3)< О(2n) < О(n!)< О(nn)
在设计算法时，我们要注意算法复杂度增量的问题，尽量避免爆炸级增量。
假设第1个月有1对初生的兔子，第2个月进入成熟期，第3个月开始生育兔子，而1对成熟的兔子每月会生1对兔子，兔子永不死去……那么，由1对初生的兔子开始，12个月后会有多少对兔子呢？
兔子数列即斐波那契数列，它的发明者是意大利数学家莱奥纳尔多·斐波那契（Leonardo Fibonacci，1170—1250）。1202年，莱奥纳尔多撰写了《算盘全书》（Liber Abaci），该书是一部较全面的初等数学著作。书中系统地介绍了印度—阿拉伯数码及其演算法则，以及中国的“盈不足术”；此外还引入了负数，并研究了一些简单的一次同余式组。
不妨拿新出生的1对小兔子分析。
第1个月，小兔子①没有繁殖能力，所以还是1对。
第2个月，小兔子①进入成熟期，仍然是1对。
第3个月，兔子①生了1对小兔子②，于是这个月共有2（1+1=2）对兔子。
第4个月，兔子①又生了1对小兔子③，因此共有3（1+2=3）对兔子。
第5个月，兔子①又生了1对小兔子④，而在第3个月出生的兔子②也生下了1对小兔子⑤，因此共有5（2+3=5）对兔子。
第6个月，兔子①②③各生下了1对小兔子，新生的3对兔子加上原有的5对兔子，这个月共有8（3+5=8）对兔子。
……
为了让表达更清楚，可用图示分别表示新生兔子、成熟期兔子和生育期兔子，兔子的繁殖过程如图1-9所示。
图1-9 兔子的繁殖过程
这个数列有如下十分明显的特点：从第3个月开始，当月的兔子数=上月兔子数+当月新生兔子数，而当月新生兔子数正好等于上上月的兔子数。因此，前面相邻两项之和便构成后一项，换言之：
当月的兔子数=上月兔子数+上上月的兔子数
斐波那契数列如下：
1，1，2，3，5，8，13，21，34，…
递归表达式如下：
那么，该如何设计算法呢？
首先按照递归表达式设计一个递归算法，见算法1-8。
//算法1-8
int Fib1(int n){
if(n==1||n==2)
return 1;
return Fib1(n-1)+Fib1(n-2);
}算法设计完之后，需要考虑如下3个问题。
● 算法是否正确？
● 算法复杂度如何？
● 算法能否改进？
上面需要考虑的第1个问题毋庸置疑，因为算法1-8是完全按照递推公式写出来的，所以正确性没有问题。那么算法复杂度呢？假设T(n)表示计算Fib1(n)所需的基本操作次数，那么：
n=1时，T(n)=1；
n=2时，T(n)=1；
n=3时，T(n)=3；//调用Fib1(2)和Fib1(1)并执行一次加法运算（Fib1(2)+Fib1(1)）因此，当n>2时需要分别调用Fib1(n−1)和Fib1(n−2)并执行一次加法运算，换言之：
n>2时，T(n)=T(n-1)+T(n-2)+1；递归表达式和时间复杂度T(n)的关系如下：
由此可得：
。
那么如何计算F(n)呢？方法有两种。
其中一种是画出F(n)的递归树，如图1-10所示。观察图1-10，递归树的左侧从n每次递减1，直到2为止，左侧树高h1=n−1；递归树的右侧从n每次递减2，直到2或1为止，右侧树高h2=n/2。高度为h2的部分是满二叉树，这部分节点数为2h2−1，即2n/2−1，总节点数大于2n/2，每个节点都需要计算，时间复杂度是指数阶的。
图1-10 F(n)的递归树
另一种是求出斐波那契数列的通项公式：
由于，因此这是一个指数阶的算法！
算法1-8的时间复杂度属于爆炸增量函数，这在算法设计中是应当避开的，那么算法1-8能不能改进呢？
斐波那契数列中的每一项（开头的两项除外）是前两项之和，如果记录前两项的值，则只需要一次加法运算就可以得到当前项的值，时间复杂度会不会更低一些呢？不妨用数组试试看，见算法1-9。
//算法1-9
int Fib2(int n){
int *F=new int[n+1];//定义一个长度为n+1的数组，空间尚未使用
F[1]=1；
F[2]=1;
for(int i=3;i<=n;i++)
F[i]=F[i-1]+F[i-2];
return F[n];
}很明显，算法1-9的时间复杂度为О(n)。因为算法1-9仍然遵从F(n)的定义，所以正确性没有问题，但时间复杂度却从算法1-8的指数阶降到了多项式阶，算法效率有了重大突破！
算法1-9使用了一个辅助数组记录中间结果，空间复杂度也为О(n)。其实我们只需要得到第n个斐波那契数，中间结果只是为了下一次使用，根本不需要记录。因此，我们可以采用迭代法进行算法设计，见算法1-10。
//算法1-10
int Fib3(int n){
if(n==1||n==2)
return 1;
int s1=1; //用s1和s2记录前面的两项
int s2=1;
for(int i=3;i<=n;i++){
int tmp=s1+s2;
s1=s2;
s2=tmp;
}
return s2;
}算法1-10使用了几个辅助变量进行迭代，时间复杂度为О(n)，但空间复杂度降到了О(1)。
问题的进一步讨论：能不能继续降阶，使算法的时间复杂度更低呢？
实质上，斐波那契数列的时间复杂度还可以降到对数阶О(logn)，有兴趣的读者可以查阅相关资料。想想看，把一个算法从指数阶降到多项式阶，再降到对数阶，这是一件多么振奋人心的事！
科学家经研究，在植物的叶、枝、茎等排列中发现了斐波那契数！例如，在树木的枝干上选一片叶子，记为数1，然后依序点数叶子（假定没有折损），直至数到与那片叶子正对的位置，则其间的叶子数多半是斐波那契数。叶子从一个位置到达下一个正对的位置称为一个循回。叶子在一个循回中旋转的圈数也是斐波那契数。在一个循回中，叶子数与叶子旋转圈数的比称为叶序（源自希腊词，意为叶子的排列）比。多数植物的叶序比呈现为斐波那契数的比。例如，蓟的头部具有34条顺时针旋转和21条逆时针旋转的斐波那契螺旋，向日葵的种子的圈数与种子数、菠萝的外部排列等同样具有这样的特性，如图1-11所示。
图1-11 斐波那契螺旋（图片来自网络）
观察延龄草、野玫瑰、南美血根草、大波斯菊、金凤花、耧斗菜、百合花、蝴蝶花的花瓣，可以发现它们的花瓣数为斐波那契数：3，5，8，13，21，…，如图1-12所示。
图1-12 植物的花瓣数（图片来自网络）
树木在生长过程中往往需要一些“休息”时间，供自身生长，而后才能萌发新枝。所以，一株树苗在一段时间（如一年）后长出一个新枝；第二年新枝“休息”，老枝依旧萌发；此后，老枝与“休息”过一年的枝同时萌发，当年新生的枝在次年“休息”。这样，一株树木各个年份的枝丫数便构成斐波那契数列，这一规律就是生物学上著名的“鲁德维格定律”。
这些植物懂得斐波那契数列吗？并非如此，它们只是按照自然规律才进化成这样。这似乎是植物排列种子的“优化方式”——能使所有种子具有相近的大小却又疏密得当，不至于在圆心处挤太多的种子而在圆周处却又很稀疏。叶子的生长方式也是如此，对于许多植物来说，每片叶子从中轴附近生长出来，为了在生长过程中一直都能最佳地利用空间（要考虑到叶子是一片一片逐渐生长出来，而不是一下子同时出现的），每片叶子和前一片叶子之间的角度应该是222.5°，这个角度被称为“黄金角度”，因为它和整个圆周（360°）之比是黄金分割数0.618的倒数，而这种生长方式就导致斐波那契螺旋的产生。向日葵的种子排列形成的斐波那契螺旋有时能达到89条，甚至144条。1992年，两位法国科学家通过对花瓣形成的过程进行计算机仿真实验，证实了在系统保持最低能量的状态下，花朵会以斐波那契数列的规律长出花瓣。
有趣的是，这样一个完全由自然数组成的数列，通项公式却是用无理数来表达的，而且当n趋向于无穷大时，斐波那契数列中的前一项与后一项的比值越来越逼近黄金分割数0.618：1÷1=1，1÷2=0.5，2÷3=0.666，…，3÷5=0.6，5÷8=0.625，…，55÷89=0.617977，…，144÷233=0.618025，…，46368÷75025=0.6180339886……
越到后面，这些比值越接近黄金分割数：
斐波那契数列起源于兔子数列，这个现实中的例子让我们真切地感到数学源于生活。在生活中，我们需要不断地透过现象发现数学问题，而不是为了学习而学习。我们学习的目的是满足自己对世界的好奇心，如果你能怀着这样一颗好奇心，或许世界会因你而不同！当斐波那契通过兔子繁殖告诉我们这种数学问题的本质——随着数列项的增加，前一项与后一项之比越来越逼近黄金分割数0.618时，我被彻底震撼，因为数学可以表达美，这是数学令我们叹为观止的地方。当数学创造出更多的奇迹时，我们会发现数学在本质上是可以回归自然的，这样的事例让我们感受到数学的美，就像黄金分割、斐波那契数列，它们如同大自然中的一朵朵小花，散发着智慧的芳香……
很多人感叹：算法为什么这么难学！
一个原因是，算法本身具有一定的复杂性。另一个原因是，讲得不到位！
算法的教与学有两个困难。
（1）我们学习了那些经典的算法，在惊叹它们奇妙的同时，难免疑虑重重：这些算法是怎么被想到的？这可能是最费解的地方。高手讲，学算法要学它的来龙去脉，包括种种证明。但对菜鸟来说，这简直比登天还难，他们很可能花费很多时间也无法搞清楚。对大多数人来说，这条路是行不通的，那怎么办呢？下功夫去记忆书上的算法？记住这些算法的效率？这样做看似学会了，其实两手空空，遇到新问题时仍无从下手。但这偏偏又是极为重要的，无论是做研究还是做实际工作，计算机专业人士最重要的能力就是解决问题——解决那些不断从实际应用中冒出来的新问题。
（2）算法作为一门学问，有两条几乎平行的线索。一条是数据结构（数据对象）：数、矩阵、集合、串、排列、图、表达式、分布等。另一条是算法策略：贪心策略、分治策略、动态规划策略、线性规划策略、搜索策略等。这两条线索是相互独立的：对于同一个数据对象上不同的问题（如单源最短路径和多源最短路径），就会用到不同的算法策略（如贪心策略和动态规划策略）；而对于完全不同的数据对象上的问题（如排序和整数乘法），也许就会用到相同的算法策略（如分治策略）。
两条线索交织在一起，该如何表述呢？我们早已习惯在一章中完全讲排序，而在另一章中完全讲图论。还没有哪一本算法书能够很好地解决这两个困难，传统的算法书大多注重内容的收录，却忽视思维过程的展示，因此我们虽然学习了经典的算法，却费解于算法设计的过程。
本书从问题出发，根据实际问题分析、设计合适的算法策略，然后在数据结构上操作实现，巧妙地将数据结构和算法策略拧成一条线。全书通过大量实例，充分展现算法设计的思维过程，让读者充分体会求解问题的思路、如何分析、使用什么算法策略、采用什么数据结构、算法的复杂性如何、是否有优化的可能等等。这里，我们培养的是让读者怀着一颗好奇心去思考问题、解决问题，更重要的是——体会学习的乐趣，发现算法的美！
本章主要说明了以下问题。
（1）将程序执行次数作为时间复杂度衡量标准。
（2）时间复杂度通常用渐近上界符号O(f(n))表示。
（3）衡量算法的好坏时通常考查算法的最坏情况。
（4）空间复杂度只计算辅助空间。
（5）递归算法的空间复杂度需要计算递归使用的栈空间。
（6）设计算法时要尽量避免爆炸级增量复杂度。
通过本章的学习，我们对算法有了初步的认识，算法就在我们的生活中。任何一个算法都不是凭空造出来的，而是来源于现实中的某个问题，由此推及一类、一系列问题，所以算法的本质是高效地解决实际问题。本章中的部分内容或许你还不是很清楚，不必灰心，还记得我在本书第 1 版的前言中所说的“大视野，不求甚解”吗？例如斐波那契数列的通项公式推导，不懂没关系，只要知道斐波那契数列用递归算法，时间复杂度是指数阶，这就够了。就像面包师一边和面，一边详细讲做好面包要多少面粉、多少酵母、多大火候，如果你对如何做面包非常好奇，大可津津有味地听下去，如果你只是饿了，那么只管吃就好了。
通过算法，你可以与世界顶级大师进行灵魂交流，体会算法的妙处。
Donald Ervin Knuth说：“程序就是蓝色的诗”。而这首诗的灵魂就是算法，走进算法，你会发现无与伦比的美！
持之以恒地学习，没有什么是学不会的。行动起来，没有什么不可以！
微信扫码关注【异步社区】微信公众号，回复“e59600”获取本书配套资源以及异步社区15天VIP会员卡，近千本电子书免费畅读。
