算法设计与分析

● 紧扣教学规律，合理设计内容结构。

● 让读者掌握现今流行技术的底层算法及复杂度分析。

● 提供电子课件等资源，方便教学。

党的二十大报告明确提出，教育、科技、人才是全面建设社会主义现代化国家的基础性、战略性支撑。必须坚持科技是第一生产力、人才是第一资源、创新是第一动力，深入实施科教兴国战略、人才强国战略、创新驱动发展战略，开辟发展新领域新赛道，不断塑造发展新动能新优势。要坚持教育优先发展、科技自立自强、人才引领驱动，加快建设教育强国、科技强国、人才强国，坚持为党育人、为国育才，全面提高人才自主培养质量，着力造就拔尖创新人才，聚天下英才而用之。

在面临经济发展转型、科学技术“卡脖子”等问题的背景下，高等教育的重点是加强基础学科、新兴学科、交叉学科建设，加快建设优势学科。计算机科学与技术学科紧跟国内外计算机科学与技术前沿，为国家培养计算机科学与技术高层次人才，而计算机科学与技术专业是一个计算机系统与网络兼顾的计算机学科宽口径专业，旨在培养具有良好的科学素养、具有自主学习意识和创新意识、科学型和工程型相结合的计算机专业高水平工程技术人才。

“算法设计与分析”是计算机科学与技术专业的核心课程，它将高级语言程序设计、数据结构和计算方法等内容紧密地结合在一起，通过介绍常见的算法设计策略、复杂性分析方法和应用，培养学生分析问题和解决问题的能力，使学生掌握算法设计的基本方法，熟悉算法分析的基本技术，并能熟练运用一些常用算法，为学生开发高效的软件系统及参加相关领域的研究工作奠定坚实的基础。

本书将社会上比较流行的、比较先进的部分互联网技术进行分析，挖掘其底层借鉴的基本算法，让读者掌握现今流行技术的底层算法及复杂度分析，提高读者的学习积极性及主动性，培养读者积极探索的科学精神。

全书共分7章：

第1章 算法概述。简单介绍了算法的概念，算法与程序的区别与联系，算法的时间复杂度和空间复杂度分析。

第2章 递归。通过实例介绍了递归方程的设计方法，同时给出求解递归方程的方法。

第3章 分治法。介绍了分治法的基本思想，并通过二分搜索、棋盘覆盖、合并排序、快速排序等应用详细介绍分治法的设计思想、时间复杂度分析。

第4章 动态规划。先由几个实例引出动态规划算法的基本思想及求解过程，然后分析了备忘录方法与动态规划算法的异同，并通过最长公共子序列、最大子段和、合唱队形问题、0-1背包问题详细介绍动态规划算法的设计方法、时间复杂度分析。

第5章 贪心算法。通过实例分析了贪心算法的设计思想、基本要素，并通过活动安排问题、背包问题、最优装载问题、哈夫曼编码等应用详细给出贪心策略的设计方法、贪心策略的证明。

第6章 回溯法。本章首先介绍解空间的基本概念，并给出构造解空间的过程分析，然后介绍回溯法的框架，并通过装载问题、n后问题、0-1背包问题等详细介绍回溯法的构造过程，最后分析了影响回溯法效率的原因。

第7章 分支限界法。本章首先介绍分支限界法与回溯法的异同，然后通过单源最短路径、装载问题、0-1背包问题详细介绍分支限界法的求解步骤。

本书采用C++语言作为表述手段，书中介绍了各种算法的设计思路、算法复杂性及实例分析，同时在每一章的章首部分增加了学习要点，每一章的章末附有和本章内容相关的习题，并免费提供电子课件。

本书的编写得到了齐鲁工业大学计算机科学与技术学部人才培养提升计划优秀教材培育项目的支持，同时得到了齐鲁工业大学教材建设基金资助，在此表示衷心的感谢。

本书由赵晶任主编，尉秀梅、李爱民、鲁芹、姜雪松任副主编，编写过程中的校对工作由硕士生邹庆志、胡玉帅、张荣环、高帅、时俊康、豆希梦、吴栋林、曲相宇、秦宥煊、石明、王浩、张雪峰完成，在此表示感谢。

由于编者的知识和写作水平有限，书稿虽几经修改，仍难免存在缺点和错误，热忱欢迎同行专家和读者惠予批评指正，使本书不断改进，日臻完善。

编 者

2022年6月

第1章 算法概述 1
1.1 算法与程序 1
1.1.1 算法与程序概述 1
1.1.2 为什么要学习算法？ 1
1.1.3 算法的描述方法 2
1.1.4 解决问题的基本步骤 4
1.2 算法的时间复杂度 5
1.2.1 算法设计的例子 5
1.2.2 为什么需要对算法进行复杂度
分析？ 8
1.2.3 算法的复杂度分析 9
1.2.4 算法时间复杂度的定义 11
1.2.5 运行时间的上界（O记号） 13
1.2.6 运行时间的下界（Ω记号） 15
1.2.7 运行时间的准确界（Θ记号） 16
1.3 算法的空间复杂度 18
1.4 NP类问题 19
习题 19
第2章 递归 21
2.1 递归算法 21
2.2 求解递归方程 28
2.2.1 迭代法 28
2.2.2 差消法 29
2.2.3 递归树法 30
2.2.4 主定理法 31
习题 34
第3章 分治法 37
3.1 分治法引言 37
3.2 分治法的基本思想 37
3.2.1 基本思想 37
3.2.2 时间复杂度分析 39
3.3 二分搜索 40
3.3.1 寻找假币 40
3.3.2 二分搜索问题 42
3.4 棋盘覆盖 44
3.5 合并排序 47
3.6 快速排序 51
3.7 金块问题 53
3.8 循环赛日程表 56
习题 58
第4章 动态规划 63
4.1 几个实例 63
4.1.1 爬楼梯问题 63
4.1.2 国王挖金矿问题 64
4.1.3 矩阵连乘问题 65
4.2 动态规划算法的基本思想 67
4.2.1 动态规划算法的特征 67
4.2.2 动态规划算法求解过程 68
4.3 备忘录方法 71
4.4 最长公共子序列 71
4.4.1 最长公共子序列问题 71
4.4.2 所有最长公共子序列 76
4.5 最大子段和 79
4.6 合唱队形问题 83
4.7 0-1背包问题 85
习题 90
第5章 贪心算法 93
5.1 贪心算法引言 93
5.1.1 贪心算法实例 93
5.1.2 贪心算法的设计思想 95
5.2 活动安排问题 96
5.3 贪心算法的基本要素 99
5.4 两种不同的背包问题 100
5.4.1 0-1背包问题 100
5.4.2 背包问题 101
5.5 最优装载问题 103
5.6 哈夫曼编码 104
5.7 单源最短路径 112
5.8 最小生成树 118
5.8.1 最小生成树性质 119
5.8.2 Prim算法 119
5.8.3 Kruskal算法 122
5.9 多机调度问题 123
习题 126
第6章 回溯法 128
6.1 回溯法引言 128
6.2 回溯法的基本思想 129
6.2.1 问题的解空间 129
6.2.2 基本思想 132
6.2.3 构造解空间的过程 133
6.3 回溯法框架 137
6.3.1 递归回溯 137
6.3.2 迭代回溯 138
6.3.3 子集树 138
6.3.4 排列树 139
6.4 装载问题 140
6.5 n皇后问题 146
6.6 0-1背包问题 151
6.7 高逐位整除数 157
6.8 图的m着色问题 159
6.9 回溯法效率分析 163
习题 164
第7章 分支限界法 165
7.1 分支限界法的基本思想 165
7.1.1 分支限界法与回溯法的异同 165
7.1.2 分支限界法求解步骤 166
7.1.3 常见的两种分支限界法 167
7.2 单源最短路径问题 178
7.3 装载问题 181
7.4 0-1背包问题 187
习题 192
参考文献 194

1. Linux系统管理（openEuler版） [主编 许兴鹍 黄君羡]
2. Web前端开发从学到用完美实践 [阮晓龙 冯顺磊 编著]
3. 用英语讲中国故事（全视频 彩色版）上、下册 [主编　谢亮亮　汪洋]
4. 新时代大学生美育教育 [穆林 刘苍劲 彭圣芳]
5. 电子商务英语 [丁文毅 严慧]
6. 智能可穿戴项目化教程 [曾文波 陈赵云]
7. 视觉设计解析与实战教程 [姜春磊　杨晓]
8. 电子产品制图与制版案例教程 [邹莉莉　苏文斌　贺小艳]
9. 设计新维度：CMF元素与创新产品设计 [彭小鹏]
10. 园林树木识别与应用 [主编 张玉泉]
11. 文本信息处理与应用 [主编　何黎松　姚香秀]
12. 工业机器人编程及应用（第二版） [主编 向艳芳 胡月霞]
13. C语言程序设计（第二版） [主编 刘祖珉 赵仕波]
14. 数据分析与应用 [主编　孙伟　王兰芹]
15. Linux操作系统配置与管理项目化教程（第二版） [主编 白玉羚 刘金明 闫 淼]
16. Ansys SpaceClaim直接建模与仿真指南 [蔡宜时 编著]
17. 基于大数据的智慧农业管理平台关键技术研究与实践 [周永福 著]
18. 健美运动 [戴显岩]
19. Python程序开发基础（AI+微课版） [赵艳莉　曾鑫]
20. 大学生心理困境突围之路 [张珏 著]
21. 机器学习基础与实践 [主编　李晓峰　胥文婷　李云波]
22. 大模型应用实战 DeepSeek＋即梦AI＋剪映重塑创作 [丁红　杨彦彦　丁丁　编著]
23. HarmonyOS从入门到精通 [陈赵云　周永福　杨　浪]
24. 用英语发现世界：欧美文化篇 [李小丽　张薇　编著]
25. 大学体育教程 [戴显岩]
26. 新一代信息技术 [李佼辉 任雪冬]
27. 轨道交通类专门用途英语教程 [李德华主编 商晔副主编]
28. 建设工程项目团队知识异质性对团队绩效的影响研究 [胡可]
29. 新时代元阳梯田 云南现代化高原立体灌区 前世 今生 未来 [云南省水利水电勘测设计研究院 ]
30. 网络工程师章节习题与考点特训（适配第6版考纲） [夏杰 编著]