《算法分析与设计》是中国大学MOOC、智慧树和学银在线一流课程配套教材，也是工科联盟和一流专业课程配套教材。全书共15章，以问题求解为主线，全面介绍问题求解的方法策略与优化技巧。主要内容包括算法与问题、算法分析、枚举算法、贪心算法、递推算法、分治算法、动态规划算法、回溯算法、分支限界、网络流算法、随机算法、计算复杂性、近似算法、图算法和字符串匹配算法。本书适合作为高等院校计算机相关专业高年级本科生和研究生的教材，也可作为ACMICPC竞赛培训和成人教育自学教材，亦可供程序设计开发人员、广大科技工作者和研究人员参考。
1.配套双一流课程2.适配课程思政和二十大精神3.以实践和能力为导向，线上开放与线下实践相结合，自动评测和互动交流相结合，专题案例与思考讨论相结合。4.适应探究性和碎片化学习，适应自主性和多样化学习，适应多元化和个性化需求，培养学生主动学习、研究和创新意识。5.适配应用型高校教学，教授十种实用算法，配套POJ竞赛题，提高实践应用能力。6.俯瞰问题解决，建构知识体系，全面介绍问题解决的基础、思想、方法，培养计算思维。
修改版前言
《算法分析与设计》（第1版）已经出版3年。在这3年时间里，人工智能、机器学习、大数据等新一代信息技术和产业蓬勃发展，科技创新成为时代潮流。为适应信息产业的创新发展需求，服务于三全育人、科教融合的四新人才培养，编者对本书第1版进行了部分修订。
本次修订保持了第1版的基本结构、主要内容和写作特色。以产业需求为导向，俯瞰问题求解，建构前沿交叉的知识体系。以实践和能力为导向，赛教融合，AI赋能，三全引领，多元探究，培养四新人才，培养学生探索交叉应用问题求解算法的思维和能力。修订版增加了第15章字符串匹配算法，介绍单模式串匹配算法和多模式串匹配算法。全书修订添加了深度多元的思考题，引领智慧创新的学习需求。拓增了算法发展历史的趣味知识、趣味生平和趣味人生，培养学生信息社会的IT素养、数字世界的工匠精神、智能时代的国际视野。此外，修订了部分习题，对原书的疏漏之处进行了订正，增加了第1、11章的混合教学示例视频。
本次修订由李恒武老师负责，感谢于瑞寒和李杰同学的审核和建议，并对广大读者提出的建议和意见表示诚挚的谢意。同时欢迎各位和读者继续对本书批评指正，提出宝贵意见。
李恒武
2025年3月
第1版前言
智能时代的今天，互联网是道开胃菜，人工智能是主菜。但不管是AlphaGo打遍天下无敌手，还是红客与黑客网络大战，程序设计都是必要的元技能。“如果你控制了代码，那就控制了世界。”这是未来学家Marc Goodman的预言，现在正在慢慢成为现实。
“Pascal之父”Nicklaus Wirth提出的公式“算法+数据结构=程序”展示了程序的本质。算法不但是程序，也是计算机科学的核心和灵魂。David Berlinski更是认为算法成就了现代世界：
“科学殿堂里陈列着两颗熠熠生辉的宝石： 一颗是微积分； 另一颗就是算法。微积分成就了现代科学，而算法成就了现代世界。”
面对各个应用领域的大量复杂问题，最重要的是建立数学模型并设计高效的求解算法。在当今复杂、海量信息的大数据处理中，好算法往往是一锤定音的利器。
本书从解决问题和应用实例入手，按照提出问题、分析问题、解决问题、总结问题的步骤，培养学生分析问题和解决问题的能力。以实践和能力为导向，线上开放与线下实践相结合，自动评测和互动交流相结合，专题案例与思考讨论相结合，聚集和重组课程内容，适应探究性和碎片化学习，适应自主性和多样化学习，适应多元化和个性化需求，培养学生主动学习、研究和创新意识。
本书共14章，主要内容包括算法与问题、算法分析、枚举算法、贪心算法、递推算法、分治算法、动态规划算法、回溯算法、分支限界、网络流算法、随机算法、计算复杂性、近似算法和图算法。
本书适合作为高等院校计算机相关专业高年级本科生和研究生的教材，也可作为ACMICPC竞赛培训和成人教育自学教材，还可作为电子工程技术人员的参考用书。
本书由李恒武老师编写。特别感谢耿蕾蕾老师和张琦乾同学的审核和建议，张琦乾同学给出全书算法示例和POJ编程习题的标准模板。在本书的编写过程中，得到了许多老师和学生的支持与帮助，在此表示诚挚的感谢！
本书是中国大学MOOC、智慧树和学银在线一流课程配套教材，也是工科联盟和一流专业课程配套教材，提供完整的视频、电子教案、知识梳理、章节测验、实践作业、思考讨论、在线题库和文档资源，便于教学和学生实践。
最后，衷心祝愿读者能够从此书中获益，从而实现自己的编程梦想。由于本书的内容较多、牵涉的技术较广，书中疏漏之处在所难免，欢迎读者在使用过程中提出宝贵意见。
李恒武
2021年4月
李恒武,博士，教授，山东省机器学习与财经数据挖掘重点实验室主任，山东省教学信息化与教学方法创新指导委员会委员。著有《web技术》《web技术设计与开发》《云计算机与大数据的应用》等，发表高水平论文40余篇，主讲《算法分析与设计》被评为线上一流课程和在线开放精品课程
目录
第1章算法与问题
1.1稳定匹配问题
1.1.1问题分析
1.1.2稳定匹配算法
1.1.3正确性证明
1.1.4算法实现
1.1.5算法总结
1.2算法概述
1.2.1算法的概念
1.2.2算法的性质
1.2.3算法与程序
1.2.4算法与问题
1.2.5问题求解
1.3问题变换
1.3.1大学入学申请
1.3.2问题变换
习题一
第2章算法分析
2.1算法分析概述
2.1.1算法选择
2.1.2分析方法
2.1.3有效算法
2.1.4事后统计
2.1.5算法分析总结
2.2渐近复杂度
2.2.1上界
2.2.2下界
2.2.3紧界
2.2.4高阶和低阶
2.2.5性质
2.3复杂度比较
2.3.1阶的高低
2.3.2比较方法
2.4实例分析
2.4.1非递归算法分析
2.4.2分析实例
2.5时空均衡
2.5.1空间复杂度
2.5.2预处理
2.5.3预构造
2.5.4图的遍历
习题二
第3章枚举算法
3.1枚举与优化
3.1.1蛮力算法
3.1.2枚举算法概述
3.1.3枚举优化
3.2组合与排列
3.2.1排列
3.2.2子集
习题三
第4章贪心算法
4.1概述
4.1.1部分背包问题
4.1.2贪心算法概述
4.2基本要素
4.2.1性质
4.2.2解证明
4.2.3预处理技巧
4.3区间问题
4.3.1区间调度问题
4.3.2区间划分问题
4.3.3区间选点问题
4.3.4区间覆盖问题
4.4MST问题
4.4.1MST特性
4.4.2Prim算法
4.4.3Kruskal算法
4.4.4逆删除算法
4.4.5MST优质性
4.5哈夫曼编码
4.5.1哈夫曼算法
4.5.2木板问题
习题四
第5章递推算法
5.1递推算法概述
5.1.1递推
5.1.2递推与递归
5.1.3递推与循环
5.1.4递归与非递归
5.1.5切分问题
5.1.6狱吏问题
5.2倒推算法
5.2.1倒推与应用
5.2.2约瑟夫问题
5.3递推求解
5.3.1快速排序
5.3.2递推方程求解
习题五
第6章分治算法
6.1分治算法概述
6.1.1设计思想
6.1.2合并排序
6.1.3基本特点
6.2分治类型
6.2.1不相似分治
6.2.2不独立分治
6.2.3三分法
6.2.4减治法
6.2.5排序算法
6.3减少子问题个数
6.3.1二分搜索
6.3.2大整数乘法
6.3.3Strassen矩阵乘法
6.4改进分治均衡度
6.4.1随机快速排序
6.4.2线性时间选择
6.5减少分解合并时间
6.5.1最接近点对问题
6.5.2计数逆序问题
习题六
第7章动态规划算法
7.1动态规划
7.1.1兔子序列
7.1.2赋权区间调度问题
7.1.3基本性质
7.1.4求解步骤
7.2决策与递推关系
7.2.1数字三角形
7.2.2多阶段决策与递推关系
7.3背包问题
7.3.101背包问题
7.3.2恰好装满背包
7.3.3完全背包
7.3.4多重背包
7.3.5混合背包
7.4区间动态规划
7.4.1矩阵相乘
7.4.2矩阵连乘
7.5DAG动态规划
7.5.1拓扑排序
7.5.2嵌套矩形
7.5.3最长不降子序列
7.5.4硬币问题
7.6树图动态规划
7.6.1最短路径问题
7.6.2FloydWarshall算法
7.6.3树状动态规划
7.7序列相似度
7.7.1LCS问题
7.7.2序列比对
7.7.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.3.3解空间结构
8.3.4算法效率
8.401背包问题
8.4.101背包问题的回溯算法
8.4.2改进上界函数
8.5n皇后问题
8.5.1n皇后问题分析
8.5.2n皇后问题的回溯算法
8.6效率改进与估计
8.6.1效率估计
8.6.2效率改进
8.6.3适用条件
习题八
第9章分支限界
9.101背包问题
9.1.101背包问题的队列式分支限界
9.1.201背包问题的优先队列式分支限界
9.1.301背包问题的优先级改进
9.2旅行商问题
9.2.1旅行商问题的优先队列式分支限界
9.2.2旅行商问题的优先级改进
9.3分支限界算法
9.3.1分支限界方式
9.3.2分支限界与回溯算法
9.3.3剪枝函数
9.3.4双向广度搜索
9.4算法总结
习题九
第10章网络流算法
10.1最大流和最小割
10.1.1最大流
10.1.2最小割
10.1.3最大流算法
10.2最大流算法改进
10.2.1容量缩放算法
10.2.2最短增广路算法
10.3预流推进算法
10.4最大流算法推广
10.4.1多源点多汇点问题
10.4.2无向图的最大流问题
10.4.3顶点容量限制问题
10.4.4带需求的流通问题
10.4.5带需求和下界的流通
10.4.6调查设计
10.5最小费用流
10.5.1最小费用路算法
10.5.2最小逃逸问题
10.6二分测试与二分匹配
10.6.1二分测试
10.6.2二分匹配
10.6.3网络流算法
10.6.4匈牙利算法
10.7应用实例
10.7.1二分匹配公式
10.7.2二分匹配应用
10.8二分图匹配
习题十
第11章随机算法
11.1随机算法概述
11.1.1确定性算法和随机算法
11.1.2随机算法分类
11.1.3伪随机数
11.1.4模运算
11.2数值随机算法
11.2.1计算π值
11.2.2计算定积分
11.3舍伍德算法
11.3.1随机快速排序算法
11.3.2随机选择算法
11.3.3随机洗牌算法
11.3.4搜索有序表
11.4拉斯维加斯算法
11.5蒙特卡洛算法
11.5.1主元素问题
11.5.2素数检测
习题十一
第12章计算复杂性
12.1P与NP
12.1.1易解与难解问题
12.1.2判定与优化问题
12.1.3计算模型
12.1.4P类
12.1.5NP类
12.1.6COOK归约与KARP归约
12.1.7多项式时间变换
12.2NP完全问题
12.2.1NP完全
12.2.2COOK定理
12.3NP完全问题证明
12.3.1局部替换技术
12.3.2分支设计技术
12.3.3限制技术
12.4NP完全问题求解
12.4.1求解策略
12.4.2子问题求解
12.4.3参数化算法
12.4.4图着色问题
12.5coNP和PSPACE
12.5.1coNP
12.5.2PSPACE
习题十二
第13章近似算法
13.1非常近似算法
13.2相对近似算法
13.2.1相对近似算法概述
13.2.2贪心
13.2.3组合技术
13.2.4定价法
13.2.5线性规划和舍入
13.3多项式时间近似方案
13.3.101背包问题的近似算法
13.3.201背包问题的多项式时间近似方案
13.3.301背包问题的完全多项式时间近似方案
习题十三
第14章图算法
14.1基本概念
14.1.1无向图与有向图
14.1.2握手定理
14.1.3图的表示
14.1.4路径
14.1.5赋权图
14.2可图性
14.2.1可图性概述
14.2.2图的同构
14.3图的遍历
14.3.1深度优先搜索
14.3.2广度优先搜索
14.4无向连通图
14.4.1无向连通图概述
14.4.2生成树
14.4.3图的连通度
14.4.4割点与桥
14.4.5双连通分量
14.4.6点连通度
14.4.7边连通度
14.5有向连通图
14.5.1有向连通图概述
14.5.2强连通分量
14.5.3拓扑排序
14.5.4传递闭包
14.6可行遍性
14.6.1无向欧拉图
14.6.2有向欧拉图
14.6.3欧拉图判定
14.6.4欧拉回路
14.6.5哈密顿图
14.7平面图
14.7.1平面图概述
14.7.2图着色问题
14.7.3图着色算法
14.7.4图的转化
习题十四
第15章字符串匹配算法
15.1单模式串匹配算法
15.1.1字符串
15.1.2KMP算法
15.1.3RK算法
15.1.4BM算法
15.1.5Sunday算法
15.2多模式串匹配算法
15.2.1Trie树
15.2.2后缀Trie的模式匹配算法
15.2.3AC自动机
习题十五
参考文献
书单推荐
