《算法设计与分析（第2版·Python版）》
主编：王秋芬
副主编：胡晨曼 彭兆军 孙育
丛书名：国家级实验教学示范中心联席会计算机学科组规划教材
定价：59.90元
印次：2-1
ISBN: 9787302709466
出版日期：2026.1
责任编辑：陈景辉
内容简介
本书依据“易理解，重实用”的指导思想，以算法设计策略为主线，沿着“问题分析—算法设计—算法描述—算法实例—算法分析—Python实践”的路线，系统地介绍算法的设计思路、分析方法及Python语言实现。全书共9章，分别为算法概述、贪心算法、分治算法、动态规划、回溯法、分支限界法、线性规划问题与网络流、随机化算法、NP完全理论。本书内容丰富、思路清晰，实例讲解详细并提供Python实现，适合作为计算机类专业及相关专业的本科生教材，也可供工程技术人员和广大读者学习参考。此外，本书也适合作为ACM程序设计竞赛的备考书或培训教材。
对于计算机科学来说,算法指的是对特定问题求解步骤的一种描述,是若干指令的有穷序列,并且它具有以下5个特性。
有限性。算法中每条指令的执行次数都是有限的,执行每条指令的时间也是有限的。也就是说,在执行若干指令之后,算法将结束。
可行性。一个算法是可行的,即算法中描述的操作都可以通过已经实现的基本运算执行有限次后实现。换句话说,要求算法中有待实现的运算都是基本的,每种运算至少在原理上能由人用纸和笔在有限的时间内完成。
在学习任何一门知识之前都要先搞清楚学习该知识的理由,即学习它的重要性。那么,为何要学习算法呢? 当然,理由有很多,这里仅给出以下5个。
(1)算法与日常生活息息相关。在日常生活中,人们都在自觉不自觉地使用算法。例如,人们到商店购买物品,会首先确定购买哪些物品,准备好所需的钱;然后确定到哪个商场选购、决定去商场的路线;若物品的质量好如何处理,对物品不满意又怎样处理,购买物品后做什么等。
(2)算法是程序的灵魂。著名的计算机科学家NiklausWirth(尼古拉斯·沃斯)提出
了著名公式:“算法+数据结构=程序”,该公式道出了算法在程序设计中的重要地位。针对具体问题,数据结构解决数据存储、数据与数据之间的关系等问题;算法解决基于选定的数据结构如何处理才能够得到问题的解,即处理步骤的问题;数据结构和算法都确定了,剩下的问题就是用某种程序设计语言将数据结构和算法翻译成程序,让计算机来解决相应的问题。所以说,数据结构是程序的基础,算法是程序的灵魂。
(3)学习算法能够提高分析问题的能力。算法本身就是要在充分理解问题的基础上,设计解决方法。该工作本身包含了计算思维和创新思维,所以学习算法可以锻炼人们的思维,提高分析问题的能力,对日后的学习、生活和工作也会产生深远的影响。
(4)算法是推动计算机行业发展的关键。计算机的每个分支都离不开算法,如云计算、大数据、人工智能、模式识别、图形图像处理等。计算机的功能越强大,人们越想尝试用它来解决更为复杂的问题,而更复杂的问题则需要更大的计算量。现代计算技术使得计算机的硬件性能得到了很大的提高,但这仅仅是为计算更复杂的问题提供了有效工具,算法的研究是使得该工具的性能得以发挥的关键。
(5)研究算法很有趣。算法充满挑战,需要精确和创新的完美结合,它时常给你带来挫折,但也让你深深入迷。当你沉浸其中时,它的速度、构思都会让你有种不可言喻的美感。
目录
第1章算法概述
1.1什么是算法
1.2为什么学习算法
1.3算法的描述方式
1.4算法设计的一般过程
1.5算法分析
1.5.1算法分析的概念
1.5.2时间复杂度和空间复杂度
1.5.3渐近复杂性态
1.5.4渐近意义下的记号
1.5.5算法的运行时间T(n)建立的依据
1.5.6算法所占用的空间S(n)建立的依据
1.6递推方程求解方法
1.6.1迭代法
1.6.2递归树
1.6.3差消法
1.6.4主方法
第2章贪心算法——贪心不足
2.1概述
2.1.1贪心算法的本质
2.1.2贪心算法的基本要素
2.2活动安排问题
2.2.1问题分析——贪心策略
2.2.2算法设计
2.2.3实例构造
2.2.4算法分析
2.2.5Python实践
2.3单源最短路径问题
2.3.1问题分析——贪心策略
2.3.2算法设计
2.3.3实例构造
2.3.4算法分析
2.3.5Python实践
目录
2.4哈夫曼编码
2.4.1问题分析——贪心策略
2.4.2算法设计
2.4.3实例构造
2.4.4算法分析
2.4.5Python实践
2.5最小生成树——Prim算法
2.5.1问题分析——贪心策略
2.5.2算法设计
2.5.3实例构造
2.5.4算法分析
2.5.5Python实践
2.6最小生成树——Kruskal算法
2.6.1问题分析——贪心策略
2.6.2算法设计
2.6.3实例构造
2.6.4算法分析
2.6.5Python实践
2.7背包问题
2.7.1问题分析——贪心策略
2.7.2算法设计
2.7.3实例构造
2.7.4算法分析
2.7.5Python实践
第3章分治算法——分而治之
3.1概述
3.1.1分治算法的本质
3.1.2分治算法的求解步骤
3.2二分查找
3.2.1问题分析——分与治的方法
3.2.2算法设计
3.2.3实例构造
3.2.4算法分析
3.2.5Python实践
3.3选第二大元素
3.3.1问题分析——分与治的方法
3.3.2算法设计
3.3.3实例构造
3.3.4算法分析
3.3.5Python实践
3.4循环赛日程表
3.4.1问题分析——分与治的方法
3.4.2算法设计
3.4.3实例构造
3.4.4算法分析
3.4.5Python实践
3.5合并排序
3.5.1问题分析——分与治的方法
3.5.2算法设计
3.5.3实例构造
3.5.4算法分析
3.5.5Python实践
3.6快速排序
3.6.1问题分析——分与治的方法
3.6.2算法设计
3.6.3实例构造
3.6.4算法分析
3.6.5Python实践
3.7线性时间选择——找第k小问题
3.7.1问题分析——分与治的方法
3.7.2算法设计
3.7.3实例构造
3.7.4算法分析
3.7.5Python实践
第4章动态规划
4.1概述
4.1.1动态规划的基本思想
4.1.2动态规划的求解步骤
4.1.3动态规划的基本要素
4.2矩阵连乘问题
4.2.1问题分析——递归关系
4.2.2算法设计
4.2.3实例构造
4.2.4算法分析
4.2.5Python实践
4.3凸多边形最优三角剖分
4.3.1问题分析——递归关系
4.3.2算法设计
4.3.3实例构造
4.3.4算法分析
4.3.5Python实践
4.4最长公共子序列问题
4.4.1问题分析——递归关系
4.4.2算法设计
4.4.3实例构造
4.4.4算法分析
4.4.5Python实践
4.5加工顺序问题
4.5.1问题分析——递归关系
4.5.2算法设计
4.5.3实例构造
4.5.4算法分析
4.5.5Python实践
4.601背包问题
4.6.1问题分析——递归关系
4.6.2算法设计
4.6.3实例构造
4.6.4算法分析
4.6.5算法的改进
4.6.6Python实践
4.7最优二叉查找树
4.7.1问题分析——递归关系
4.7.2算法设计
4.7.3实例构造
4.7.4算法分析
4.7.5Python实践
第5章回溯法——深度优先搜索
5.1概述
5.2典型的解空间结构
5.2.1子集树
5.2.2排列树
5.2.3满m叉树
5.301背包问题——子集树
5.3.1问题分析——解空间及搜索条件
5.3.2算法设计
5.3.3实例构造
5.3.4算法的改进
5.3.5算法分析
5.3.6Python实践
5.4最大团问题——子集树
5.4.1问题分析——解空间及搜索条件
5.4.2算法设计
5.4.3实例构造
5.4.4算法分析
5.4.5Python实践
5.5批处理作业调度问题——排列树
5.5.1问题分析——解空间及搜索条件
5.5.2算法设计
5.5.3实例构造
5.5.4算法分析
5.5.5Python实践
5.6旅行商问题——排列树
5.6.1问题分析——解空间及搜索条件
5.6.2算法设计
5.6.3实例构造
5.6.4算法分析
5.6.5Python实践
5.7图的m着色问题——满m叉树
5.7.1问题分析——解空间及搜索条件
5.7.2算法设计
5.7.3实例构造
5.7.4算法分析
5.7.5Python实践
5.8最小质量机器设计问题——满m叉树
5.8.1问题分析——解空间及搜索条件
5.8.2算法设计
5.8.3实例构造
5.8.4算法分析
5.8.5Python实践
第6章分支限界法——宽度优先或最小耗费(最大效益)
优先搜索
6.1分支限界法的基本思想
6.201背包问题
6.3旅行商问题
6.4布线问题
6.4.1问题分析——解空间及搜索条件
6.4.2算法设计
6.4.3实例构造
6.4.4算法分析
6.4.5Python实践
6.5分支限界法与回溯法的比较
第7章线性规划问题与网络流
7.1线性规划问题
7.1.1一般线性规划问题的描述
7.1.2标准型线性规划问题的描述
7.1.3标准型线性规划问题的单纯形算法
7.2最大网络流
7.2.1基本概念
7.2.2增广路算法
7.2.3最大网络流的变换与应用
7.3最小费用最大流
7.3.1基本概念
7.3.2消圈算法
7.3.3最小费用最大流的变换与应用
第8章随机化算法
8.1概述
8.1.1随机化算法的类型及特点
8.1.2随机数发生器
8.2数值随机化算法
8.2.1计算π的值
8.2.2计算定积分
8.3蒙特卡洛算法
8.3.1主元素问题
8.3.2素数测试
8.4拉斯维加斯算法
8.4.1整数因子分解
8.4.2n皇后问题
8.5舍伍德算法
8.5.1随机快速排序
8.5.2线性时间选择
第9章NP完全理论
9.1易解问题和难解问题
9.2P类和NP类问题
9.2.1P类问题
9.2.2NP类问题
9.3NP完全问题
9.3.1多项式变换技术
9.3.2典型的NP完全问题
9.4NP完全问题的近似算法
9.4.1顶点覆盖问题
9.4.2装箱问题
9.4.3旅行商问题
9.4.4集合覆盖问题
参考文献
10个月宝宝每天需要喝多少奶粉？
