✍ Scribed by 程振波; 李曲; 王春平
No coin nor oath required. For personal study only.
算法设计与分析是计算机专业⾮常重要的⼀门基础课程，它不仅是诸多计
算机专业课程的基础，也是许多信息科技类公司在招聘程序员时，笔试与⾯试
重点考核的内容。算法设计与分析已经有了诸多经典的著作，⽐如美国⿇省理
⼯（MIT）⼏位教授合著的《算法导论》1等。然⽽，这些经典著作当作教材使
⽤时，都会存在对内容进⾏适当裁剪，以便它更适合48 或者32 个学时教学的
问题。我们写本书的⽬的就是对初等算法内容进⾏合理的编排，让初学者能很
快地掌握解决计算问题的常⽤算法，以及分析算法效率的⽅法。
本书算法均采⽤Python 语⾔进⾏描述，Python 是⼀类解释性语⾔，其语法
简单直观，有⼀定程序设计基础的学⽣可以很快⼊门。Python 语法简单并不意
味着功能弱，它在科学计算、Web 应⽤等诸多领域都有着⼴泛的应⽤。国外知
名的⾼校，如⿇省理⼯，也在算法设计课中采⽤Python 语⾔描述。与采⽤伪代
码描述算法的书⽐较⽽⾔，采⽤Python 描述算法能有直接可运⾏的代码，从⽽
可以帮助读者更易于去揣摩算法实现的技巧。
计算机算法不仅涉及诸多理论，还有各种技术细节。⽐如介绍随机算法时，
有些执⾏时间的分析就需要较多的概率论知识；⽽算法实现技术细节则不仅关
注如何存储数据，甚⾄对执⾏算法的硬件环境也会考虑在内。本书的内容安排
则希望在算法的数学分析和实现之间取得⼀个合理的平衡。⾸先，在分析算法
效率时尽量避免过深的数学证明，但关键步骤依然会给出直观的解释。其次，在
实现算法时本书尽量利⽤Python 内已有的数据结构和库函数，从⽽简化算法实现的技术难度。
如果将要处理的数据、问题看作是⾷材，那么算法就是将⾷材“转化”成各种
令⼈垂诞美⾷的过程。中国菜肴到处都是充满想象⼒的转化，将原本普通的⾷
材（⼤⾖和糯⽶等）转化为营养和美味的⾷物（⾖腐、酒酿和酱料等等）。本书的
主线就是转化，它不仅有问题的转化，也有⽅法的转化（如图1所⽰）。通过问题
的转化将问题“化繁为简”，通过⽅法的转化以便融会贯通各种算法设计的技巧。
由于计算机已经成为现代科技、⽣活不可缺少的⼯具。因此，解决计算问
题的算法涉及的内容可以说包罗万象，从简单的排序和查找到复杂的语⾳识别、
⽂字翻译，甚⾄游戏等等都离不开算法。本书内容涵盖了⼤部分的经典算法，主
要内容包括递归算法、分治算法、排序算法、动态规划算法、图遍历算法、最⼤
流算法、随机算法和计算问题分类。
封面
扉页
内容简介
版权页
前言
目录
第1章 引言
1.1 算法的定义
1.2 算法设计与分析举例
1.3 小结
课后习题
第2章 渐进分析与Python计算模型
2.1 引言
2.2 计算模型
2.3 算法的渐进分析
2.4 Python计算模型
2.5 算法分析实例
2.6 小结
课后习题
第3章 问题求解与代码优化
3.1 引言
3.2 文档比较
3.3 拼写矫正
3.4 稳定匹配问题
3.5 小结
课后习题
第4章 递归算法与递归函数
4.1 引言
4.2 递归的组成结构
4.3 递归算法的执行
4.4 利用递归算法求解问题
4.5 递归函数的求解
4.6 小结
课后习题
第5章 排序与树结构
5.1 引言
5.2 递归与排序
5.3 二叉搜索树
5.4 堆
5.5 小结
课后习题
第6章 分治算法
6.1 引言
6.2 股票的买卖
6.3 统计逆序
6.4 空间最小距离点对
6.5 寻找第k 小的数
6.6 大整数乘法
6.7 小结
课后习题
第7章 图搜索算法
7.1 引言
7.2 图搜索的应用
7.3 图的表示
7.4 宽度优先搜索
7.5 深度优先搜索
7.6 小结
课后习题
第8章 贪心算法
8.1 引言
8.2 硬币找零
8.3 间隔任务规划
8.4 单源最矩路径问题
8.5 最小生成树
8.6 小结
课后习题
第9章 动态规划算法
9.1 引言
9.2 再遇斐波那契数
9.3 一维动态规划
9.4 二维动态规划
9.5 小结
课后习题
第10章 最大流算法应用
10.1 引言
10.2 最大流算法
10.3 最大流算法的应用
10.4 小结
课后习题
第11章 随机算法
11.1 引言
11.2 矩阵乘积结果验证
11.3 快速排序
11.4 选择第k 小的数
11.5 寻找最小割边
11.6 小结
课后习题
第12章 算法复杂度
12.1 引言
12.2 问题的分类
12.3 NPC 问题应用
12.4 P等于NP吗
12.5 小结
课后习题
正文结束
索引
代码列表
参考文献
📜 SIMILAR VOLUMES
内容简介 · · · · · · 《算法设计与分析》系统地介绍算法设计与分析的概念和方法，共四部分内容，第一部分包括前两章，介绍算法设计与分析的基本概念及必要的数学工具，对算法的时间复杂性的概念及算法的分析方法作了较为详细的叙述。第二部分包括第3~~9章，以算法设计技术为纲，从排序问题和离散集合的操作开始，进而介绍递归技术、分治法、贪婪法、动态规划、回溯法、分支与限界法以及随机算法等算法设计技术及其复杂性。第三部分包括第10章和第11章，介绍计算机应用领域里的一些算法，如图和网络中的一些问题，以及计算几何中的一些问题。第四部分包括第12~~15章，介绍算法设计与分析中的一些理论问题，如NP
作者简介 · · · · · · 莱维丁是Villanova大学计算科学系的教授。他的论文 A New Road Map of Algorithm Design Techniques:Picking Up Where the Traditional Classification Leaves Off（《算法设计技术新途径：弥补传统分类法的缺憾》）受到业内人士极高的评价。在SIGCSE会议上，作者做过多次关于算法教学的演讲。
内容简介 · · · · · · 本书是国际著名算法专家李德财教授主编的系列丛书“Lecture Notes Series on Computing”中的一本。本书涵盖了绝大多数算法设计中的一般技术，在表达每一种技术时，阐述它的应用背景，注意用与其他技术比较的方法说明它的特征，并提供大量相应实际问题的例子。本书同时也强调了对每一种算法的详细的复杂性分析。全书分七部分19章，从算法设计和算法分析的基本概念和方法入手，先后介绍了递归技术、分治、动态规划、贪心算法、图的遍历等技术，对NP完全问题进行了基本但清楚的讨论。对概率算法、近似算法和计算几何这些近年来发展迅猛的领域也用一定的篇幅讲述了基本
书签已装载， 书签制作方法请找 [email protected] 完全免费 本书在介绍算法时，重点介绍用干设计算法的策略．非常与众不同。书中介绍了剪枝搜索、分摊分析、随机算法、在线算法以及多项式近似方案等相对较新的思想和众多基于分摊分析新开发的算法，每个算法都与实例一起加以介绍，而且每个例子都利用图进行详细解释。此外，本书还提供了超过400幅图来帮助初学者理解。本书适合作为高等院校算法设计与分析课程的高年级本科生和低年级研究生的教材，也可供相美科技人员和专业人七参考使用。
<p>计算机算法设计与分析，ISBN：9787505363915，作者：王晓东编著</p>